<abstract xmlns="http://www.w3.org/1999/xhtml"><p>Parallel Communicating Grammar Systems (PCGS) were introduced as a language-theoretic treatment of concurrent systems. A PCGS extends the concept of a grammar to a structure that consists of several grammars working in parallel, communicating with each other, and so contributing to the generation of strings. PCGS are usually more powerful than a single grammar of the same type; PCGS with context-free components (CF-PCGS) in particular were shown to be Turing complete. However, this result only holds when a specific type of communication (which we call broadcast communication, as opposed to one-step communication) is used. We expand the original construction that showed Turing completeness so that broadcast communication is eliminated at the expense of introducing a significant number of additional, helper component grammars. We thus show that CF-PCGS with one-step communication are also Turing complete. We introduce in the process several techniques that may be usable in other constructions and may be capable of removing broadcast communication in general. </p></abstract>

Parallel Communicating Grammar Systems (PCGS) were introduced as a language-theoretic treatment of concurrent systems. A PCGS extends the concept of a grammar to a structure that consists of several grammars working in parallel, communicating with each other, and so contributing to the generation of strings. PCGS are usually more powerful than a single grammar of the same type; PCGS with context-free components (CF-PCGS) in particular were shown to be Turing complete. However, this result only holds when a specific type of communication (which we call broadcast communication, as opposed to one-step communication) is used. We expand the original construction that showed Turing completeness so that broadcast communication is eliminated at the expense of introducing a significant number of additional, helper component grammars. We thus show that CF-PCGS with one-step communication are also Turing complete. We introduce in the process several techniques that may be usable in other constructions and may be capable of removing broadcast communication in general.

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

Department of Computer Science Bishop's University Sherbrooke, Quebec J1M 1Z7,

Acta Universitatis Sapientiae, Informatica

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Parallel Communicating Grammar Systems (PCGS) were introduced as a language-theoretic treatment of concurrent systems. A PCGS extends the concept of a grammar...

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

Published Online: Dec 30, 2016

Page range: 113 - 170

Received: Oct 10, 2016

DOI: https://doi.org/10.1515/ausi-2016-0007

Keywords
formal languages, theory of computation, formal grammar, parallel communicating grammar system, Turing completeness

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

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

Published Online: Dec 30, 2016

Page range: 113 - 170

Received: Oct 10, 2016

DOI: https://doi.org/10.1515/ausi-2016-0007

Keywordsformal languages, theory of computation, formal grammar, parallel communicating grammar system, Turing completeness

© 2017

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 License.

Keywords
formal languages, theory of computation, formal grammar, parallel communicating grammar system, Turing completeness