On the computational completeness of context-free parallel communicating grammar systems

Authors
Csuhaj-Varju, E Vaszil, G
Citation
E. Csuhaj-varju et G. Vaszil, On the computational completeness of context-free parallel communicating grammar systems, THEOR COMP, 215(1-2), 1999, pp. 349-358
Citations number
9
Categorie Soggetti
Computer Science & Engineering
Journal title
THEORETICAL COMPUTER SCIENCE
ISSN journal
03043975 → ACNP
Volume
215
Issue
1-2
Year of publication
1999
Pages
349 - 358
Database
ISI
SICI code
0304-3975(19990228)215:1-2<349:OTCCOC>2.0.ZU;2-O
Abstract
We prove that all recursively enumerable languages can be generated by cont ext-free returning parallel communicating grammar systems by showing how th e parallel communicating grammars can simulate two-counter machines, a clas s of Turing machine variants which is known to be computationally complete. Moreover, we prove that systems with a bounded number of components are su fficient to reach this generative power. (C) 1999-Elsevier Science B.V. All rights reserved.