Completeness of context-free grammar forms

DOI10.1016/0022-0000(81)90001-5zbMath0477.68085OpenAlexW2055050583MaRDI QIDQ1160491

Hermann Maurer, Arto Salomaa, Derick Wood

Publication date: 1981

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0022-0000(81)90001-5

zbMATH Keywords

expansion spectrumcomplete grammar formshierarchies of context-free languages familiessuper normal form theorem

Mathematics Subject Classification ID

Formal languages and automata (68Q45)

Cites Work

• Unnamed Item
• Grammar and L forms: an introduction
• Context-free grammar forms with strict interpretations
• On generators and generative capacity of EOL forms
• Colorings and interpretations: a connection between graphs and grammar forms
• Position-restricted grammar forms and grammars
• Decidability and density in two-symbol grammar forms
• Context-free grammar forms
• EOL forms
• Dense Hierarchies of Grammatical Families
• Uniform interpretations of L forms
• On strict interpretations of grammar forms