On the computational completeness of context-free parallel communicating grammar systems

DOI10.1016/S0304-3975(98)00193-5zbMath0915.68108OpenAlexW1995375035MaRDI QIDQ1287096

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

Publication date: 29 April 1999

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

Full work available at URL: https://doi.org/10.1016/s0304-3975(98)00193-5

zbMATH Keywords

context-free returning parallel communicating grammar systemsrecursively enumerable languages

Mathematics Subject Classification ID

Grammars and rewriting systems (68Q42)

Related Items (7)

PC grammar systems with five context-free components generate all recursively enumerable languages. ⋮ Parallel communicating grammar systems with context-free components are Turing complete for any communication model ⋮ On context-free parallel communicating grammar systems: Synchronization, communication, and normal forms ⋮ Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts ⋮ PC GRAMMAR SYSTEMS WITH CLUSTERS OF COMPONENTS ⋮ Computing with membranes ⋮ Parallel communicating grammar systems with bounded resources

Cites Work

• Nonreturning PC grammar systems can be simulated by returning systems
• On the computational power of context-free PC grammar systems
• Turing machines with restricted memory access
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: On the computational completeness of context-free parallel communicating grammar systems