Parameter-reduction of higher level grammars (Q1099634)

The author's abstract describes quite appropriately this long and technical paper: ``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 parameter-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.''