PC grammar systems with five context-free components generate all recursively enumerable languages.

DOI10.1016/S0304-3975(02)00852-6zbMath1042.68057MaRDI QIDQ1874424

Erzsébet Csuhaj-Varjú, György Vaszil, Gheorghe Păun

Publication date: 25 May 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00852-6

zbMATH Keywords

Descriptional complexity; Recursively enumerable languages; Parallel communicating grammar systems

Mathematics Subject Classification ID

68Q45: Formal languages and automata

68Q42: Grammars and rewriting systems

Related Items

Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts, On the Number of Components and Clusters of Non-returning Parallel Communicating Grammar Systems, Improved descriptional complexity results on generalized forbidding grammars, Parallel communicating grammar systems with context-free components are Turing complete for any communication model, PC GRAMMAR SYSTEMS WITH CLUSTERS OF COMPONENTS, REMARKS ON CONTEXT-FREE PARALLEL COMMUNICATING GRAMMAR SYSTEMS GENERATING CROSSED AGREEMENTS

Cites Work

• On the computational completeness of context-free parallel communicating grammar systems
• On the computational power of context-free PC grammar systems
• Parallel communicating grammar systems with bounded resources
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item