Scattered context grammars generate any recursively enumerable language with two nonterminals

DOI10.1016/j.ipl.2010.07.008zbMath1234.68175OpenAlexW1970665412MaRDI QIDQ407598

György Vaszil, Erzsébet Csuhaj-Varjú

Publication date: 27 March 2012

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2010.07.008

zbMATH Keywords

formal languagesregulated rewritingnonterminal complexityscattered context grammars

Mathematics Subject Classification ID

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

Related Items

Nonterminal complexity of one-sided random context grammars ⋮ Language classes generated by tree controlled grammars with bounded nonterminal complexity ⋮ Scattered Context Grammars with One Non-Context-Free Production are Computationally Complete ⋮ Nonterminal complexity of tree controlled grammars ⋮ Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the descriptional complexity of scattered context grammars
• Terminating left-hand sides of scattered context productions M. Nivat
• Generative power of three-nonterminal scattered context grammars
• Scattered context grammars
• Turing machines with restricted memory access