Helmut Seidl. A quadratic regularity test for non-deleting macro S grammars. In Lothar Budach, editor, Fundamentals of Computation Theory, volume 199 of Lecture Notes in Computer Science, pages 422-430, Cottbus, Germany, September 1985. Springer.
A quadratic regularity test is presented for non-deleting simple deterministic contextfree tree grammars as well as for non-deleting macro S grammars.
Reference: Bibtex The original publication is available at www.springerlink.com