A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

DOI10.1016/S0020-0190(03)00202-3zbMath1162.68467MaRDI QIDQ1007611

Henning Fernau, Alexander Meduna

Publication date: 23 March 2009

Published in: Information Processing Letters (Search for Journal in Brave)

zbMATH Keywords

reductionformal languagesscattered context grammarscontext sensitive productions

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Grammars and rewriting systems (68Q42)

Related Items (6)

Nonterminal complexity of one-sided random context grammars ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Comparison of some descriptional complexities of 0L systems obtained by a unifying approach ⋮ On the descriptional complexity of some rewriting mechanisms regulated by context conditions ⋮ Nonterminal complexity of tree controlled grammars ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity

Cites Work

• Unnamed Item
• On the degree of scattered context-sensitivity.
• Generative power of three-nonterminal scattered context grammars
• Scattered context grammars

This page was built for publication: A simultaneous reduction of several measures of descriptional complexity in scattered context grammars