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