Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts

DOI10.1007/978-3-319-46376-6_8zbMath1396.68062OpenAlexW2547510902MaRDI QIDQ4686650

Mary Sarah Ruth Wilkin, Stefan D. Bruda

Publication date: 4 October 2018

Published in: Emergent Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-46376-6_8

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Parallel communicating grammar systems with context-free components are Turing complete for any communication model
• Nonreturning PC grammar systems can be simulated by returning systems
• On the computational completeness of context-free parallel communicating grammar systems
• Testing equivalences for processes
• On the computational power of context-free PC grammar systems
• PC grammar systems with five context-free components generate all recursively enumerable languages.
• Further remarks on parallel communicating grammar systems
• On the Number of Components and Clusters of Non-returning Parallel Communicating Grammar Systems
• Tools and Algorithms for the Construction and Analysis of Systems
• Turing machines with restricted memory access
• Parallel communicating grammar systems with terminal transmission

This page was built for publication: Emergence in Context-Free Parallel Communicating Grammar Systems: What Does and Does not Make a Grammar System More Expressive Than Its Parts