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 $(OI-)$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 $G$ of level n>0 which generates at least one term we construct grammars $R(G)$ and $P(G)$ such that $R(G)$ and $P(G)$ generate the same language as $G$ 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