Non-returning PC grammar systems generate any recursively enumerable language with eight context-free components

DOI10.25596/JALC-2007-307MaRDI QIDQ3517110zbMATH OpenFDO

Authors György Vaszil

Publication date 12 August 2008

Full work available at URL https://doi.org/10.25596/JALC-2007-307

zbMATH Keywords

descriptional complexityparallel communicating grammar systems

Mathematics Subject Classification ID

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

Recommendations

• On the size complexity of non-returning context-free PC grammar systems
• PC grammar systems with five context-free components generate all recursively enumerable languages.
• On the computational power of context-free PC grammar systems
• scientific article; zbMATH DE number 878951
• On simulating non-returning PC grammar systems with returning systems

Cited in

(7)

• On simulating non-returning PC grammar systems with returning systems
• A remark on evolutionary systems
• PC grammar systems with five context-free components generate all recursively enumerable languages.
• On centralized PC grammar systems with context-sensitive components
• Scattered context grammars generate any recursively enumerable language with two nonterminals
• scientific article; zbMATH DE number 2162201 (Why is no real title available?)
• On the size complexity of non-returning context-free PC grammar systems

This page was built for publication: Non-returning PC grammar systems generate any recursively enumerable language with eight context-free components

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