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

*(English)*Zbl 1404.68064Summary: 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.

##### MSC:

68Q42 | Grammars and rewriting systems |

68Q10 | Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) |

68Q15 | Complexity classes (hierarchies, relations among complexity classes, etc.) |

68Q45 | Formal languages and automata |

##### Keywords:

formal languages; theory of computation; formal grammar; parallel communicating grammar system; Turing completeness
PDF
BibTeX
XML
Cite

\textit{M. S. R. Wilkin} and \textit{S. D. Bruda}, Acta Univ. Sapientiae, Inform. 8, No. 2, 113--170 (2016; Zbl 1404.68064)

Full Text:
DOI

##### References:

[1] | S. D. Bruda, M. S. R. Wilkin, Parse trees for context-free parallel communicating grammar systems, Proc. 13th International Conference on Automation and Information (ICAI 12), Iasi, Romania, June 2012, pp. 144-149. =M14 |

[2] | E. Csuhaj-Varjú, G. Păun, G. Vaszil, PC grammar systems with five context-free components generate all recursively enumerable languages. Theoretical Computer Science 299 (2003) 785-794. ⇒119, 121, 124, 167, 168 · Zbl 1042.68057 |

[3] | E. Csuhaj-Varjú, On size complexity of context-free returning parallel communicating grammar systems, in: Where Mathematics, Computer Scients, Linguistics and Biology Meet, (ed. C. Martin-Vide and V. Mitrana). Springer, 2001, pp. 37- 49. ⇒119, 121, 124, 167 · Zbl 1007.68089 |

[4] | E. Csuhaj-Varjú, G. Vaszil, On the computational completeness of context-free parallel communicating grammar systems, Theoretical Computer Science, 215 (1999) 349-358. ⇒115, 119, 121, 124, 125, 126, 129, 141, 150, 167, 168 · Zbl 0915.68108 |

[5] | E. Csuhaj-Varjú, G. Vaszil, On the size complexity of non-returning context- free PC grammar systems, Proc. 11th International Workshop on Descńptional Complexity of Formal Systems (DCFS 2009), Magdeburg, Germany. 2009, pp. 91-100. ⇒119, 121, 168 |

[6] | E. Csuhaj-Varjú, J. Dassow, J. Kelemen, G. Păun, Grammar Systems: A Grammatical Approach to Distribution and Cooperation, Gordon and Breach, 1994. ⇒114, 115, 116, 118, 119, 124 |

[7] | J. Dassow, G. Păun, G. Rozenberg, Grammar systems, in: Handbook of Formal Languages - Volume 2. Linear Modeling: Background and Applications, Springer, 1997. pp. 155-213. ⇒119 |

[8] | S. Diunitrescu, Nonreturning PC grammar systems can be simulated by returning systems. Theoretical Computer Science, 165 (1996) 463-474. ⇒ 114, 121, 168 · Zbl 0872.68099 |

[9] | P. C. Fischer, Turing machines with restricted memory access, Information and Computation, 9 (1966) 364-379. ⇒115, 126 · Zbl 0145.24205 |

[10] | M. R. Garey, D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Macmillan Higher Education, 1979. ⇒116 · Zbl 0411.68039 |

[11] | V. Geffert, Context-free-like forms for the phrase-structure grammars, Mathematical Foundations of Computer Science, Lecture Notes in Computer Science, 324 (1988) 309-317. ⇒119 · Zbl 0652.68095 |

[12] | G. Katsirelos, S. Maneth, N. Narodytska, T. Walsh, Restricted global grammar contraints, Proc. Principles and Practice of Constraint Programming (CP 2009), Lecture Notes in Computer Science, 5732 (2009) 501 508. ⇒116 |

[13] | H. R. Lewis, C. H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 2nd edition, 1998. ⇒116 |

[14] | N. Mandache, On the computational power of context-free PC grammar systems, Theoretical Computer Science, 237 (2000) 135-148. ⇒114, 121, 168 · Zbl 0939.68058 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.