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

DOI10.1515/AUSI-2016-0007MaRDI QIDQ508542zbMATH OpenOpenAlexFDO

Authors Mary Sarah Ruth Wilkin, Stefan D. Bruda

Publication date 7 February 2017

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

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

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

zbMATH Keywords

formal grammarformal languagesparallel communicating grammar systemtheory of computationTuring completeness

Mathematics Subject Classification ID

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

Recommendations

• On the computational completeness of context-free parallel communicating grammar systems
• scientific article; zbMATH DE number 5271
• scientific article; zbMATH DE number 878943
• scientific article; zbMATH DE number 1502103
• PC grammar systems with five context-free components generate all recursively enumerable languages.

Cites work

• scientific article; zbMATH DE number 4064526 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 745858 (Why is no real title available?)
• scientific article; zbMATH DE number 1836409 (Why is no real title available?)
• 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
• 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.
• Reformulating Global Grammar Constraints
• Turing machines with restricted memory access

Cited in

(2)

• scientific article; zbMATH DE number 8777 (Why is no real title available?)
• Emergence in context-free parallel communicating grammar systems: what does and does not make a grammar system more expressive than its parts

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

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