Helmut Seidl. Parameter-Reduction of Higher Level Grammars (Extended Abstract). In Max Dauchet and Maurice Nivat, editors, Trees in Algebra and Programming, volume 299 of Lecture Notes in Computer Science, pages 52-71, Nancy, France, March 1988. Springer.
A higher level grammar is called terminating, if for every accessible term t there is at least one terminal term which can be derived from t. A grammar is called parameter-reduced, if it is terminating and has no superfluous parameters. For every grammar of level n>0 which generates at least one term we construct grammars and such that and generate the same language as but are terminating and paramter-reduced, respectively. We introduce a hierarchy of restrictions to the deletion capability of the grammars which allow a gradual decrease in the complexity of the algorithms from n-iterated exponential time to polynomial time.
Download: PDF Reference: Bibtex The original publication is available at www.springerlink.com