Scattered context grammars generate any recursively enumerable language with two nonterminals
From MaRDI portal
Publication:407598
DOI10.1016/J.IPL.2010.07.008zbMATH Open1234.68175OpenAlexW1970665412MaRDI QIDQ407598FDOQ407598
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
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
- 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 (8)
- Uniform generation of languages by scattered context grammars
- 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)
