Parallel communicating grammar systems with context-free components are Turing complete for any communication model

DOI10.1515/AUSI-2016-0007zbMath1404.68064OpenAlexW2576274719MaRDI QIDQ508542

Stefan D. Bruda, Mary Sarah Ruth Wilkin

Publication date: 7 February 2017

Published in: Acta Universitatis Sapientiae. Informatica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1515/ausi-2016-0007

zbMATH Keywords

formal languagestheory of computationTuring completenessformal grammarparallel communicating grammar system

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Grammars and rewriting systems (68Q42) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

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

Cites Work

• Nonreturning PC grammar systems can be simulated by returning systems
• On the computational completeness of context-free parallel communicating grammar systems
• On the computational power of context-free PC grammar systems
• PC grammar systems with five context-free components generate all recursively enumerable languages.
• Reformulating Global Grammar Constraints
• Turing machines with restricted memory access
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Parallel communicating grammar systems with context-free components are Turing complete for any communication model