Generative power of three-nonterminal scattered context grammars

DOI10.1016/S0304-3975(00)00153-5zbMath0949.68080MaRDI QIDQ1583096

Alexander Meduna

Publication date: 26 October 2000

Published in: Theoretical Computer Science (Search for Journal in Brave)

zbMATH Keywords

scattered context grammars

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (11)

Scattered context grammars generate any recursively enumerable language with two nonterminals ⋮ On the degree of scattered context-sensitivity. ⋮ Nonterminal complexity of programmed grammars. ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Canonical scattered context generators of sentences with their parses ⋮ Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete ⋮ 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 ⋮ On the descriptional complexity of scattered context grammars ⋮ A simultaneous reduction of several measures of descriptional complexity in scattered context grammars

Cites Work

• On the generative power of regular pattern grammars
• Terminating left-hand sides of scattered context productions M. Nivat

This page was built for publication: Generative power of three-nonterminal scattered context grammars