Parameter-reduction of higher level grammars

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


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 n0 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 delection capability of the grammars which allow a gradual decrease in the complexity of the algorithms from n-iterated exponential time to polynomial time.

Original languageEnglish
Pages (from-to)47-85
Number of pages39
JournalTheoretical Computer Science
Issue number1
StatePublished - Nov 1987
Externally publishedYes


Dive into the research topics of 'Parameter-reduction of higher level grammars'. Together they form a unique fingerprint.

Cite this