Scattered context grammars generate any recursively enumerable language with two nonterminals

DOI10.1016/J.IPL.2010.07.008zbMATH Open1234.68175OpenAlexW1970665412MaRDI QIDQ407598FDOQ407598

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

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

zbMATH Keywords

formal languagesnonterminal complexityregulated rewritingscattered context grammars

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• 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
• Refining the nonterminal complexity of graph-controlled, programmed, and matrix grammars
• Title not available (Why is that?)
• Title not available (Why is that?)
• Turing machines with restricted memory access

Cited In (10)

• 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
• Language Classes Generated by Tree Controlled Grammars with Bounded Nonterminal Complexity
• Generative power of three-nonterminal scattered context grammars
• Language classes generated by tree controlled grammars with bounded nonterminal complexity
• Nonterminal complexity of one-sided random context grammars
• Nonterminal complexity of tree controlled grammars
• 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

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)