Scattered context grammars generate any recursively enumerable language with two nonterminals

DOI10.1016/J.IPL.2010.07.008MaRDI QIDQ407598zbMATH OpenOpenAlexFDO

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

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 languagesnonterminal complexityregulated rewritingscattered context grammars

Mathematics Subject Classification ID

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

Recommendations

• On the descriptional complexity of scattered context grammars
• Generative power of three-nonterminal scattered context grammars
• Four-nonterminal scattered context grammars characterize the family of recursively enumerable languages
• Non-returning PC grammar systems generate any recursively enumerable language with eight context-free components
• Nonterminal complexity of one-sided random context grammars

Cites work

• scientific article; zbMATH DE number 4064526 (Why is no real title available?)
• scientific article; zbMATH DE number 2013189 (Why is no real title available?)
• scientific article; zbMATH DE number 3413820 (Why is no real title available?)
• Generative power of three-nonterminal scattered context grammars
• On the descriptional complexity of scattered context grammars
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Scattered context grammars
• Terminating left-hand sides of scattered context productions M. Nivat
• Turing machines with restricted memory access

Cited in

(11)

• Scattered context grammars with one non-context-free production are computationally complete
• Six nonterminals are enough for generating each r.e. language by a matrix grammar
• Uniform generation of languages by scattered context grammars
• On the descriptional complexity of scattered context grammars
• Bounded number of parallel productions in scattered context grammars with three nonterminals
• Generative power of three-nonterminal scattered context grammars
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Nonterminal complexity of tree controlled grammars
• Nonterminal complexity of one-sided random context grammars
• Descriptional complexity of three-nonterminal scattered context grammars: an improvement

This page was built for publication: Scattered context grammars generate any recursively enumerable language with two nonterminals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q407598)