Helmut Seidl. Parameter Reduction of Higher Level Grammars. Theor. Comput. Sci., 55(1):47-85, 1987.

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