On the computational capacity of parallel communicating finite automata
- Systems of parallel finite automata communicating by states are investigated. We consider deterministic and nondeterministic devices and distinguish four working modes. It is known that systems in the most general mode are as powerful as one-way multi-head finite automata. Here we solve some open problems on the computational capacity of systems working in the remaining modes. In particular, it is shown that deterministic returning and non-returning devices are equivalent, and that there are languages which are accepted by deterministic returning and centralized systems but cannot be accepted by deterministic non-returning centralized systems. Furthermore, we show that nondeterministic systems are strictly more powerful than their deterministic variants in all the four working modes. Finally, incomparability with the classes of (deterministic) (linear) context-free languages as well as the Church-Rosser languages is derived.
Author details: | Henning BordihnORCiD, Martin Kutrib, Andreas Malcher |
---|---|
DOI: | https://doi.org/10.1142/S0129054112500062 |
ISSN: | 0129-0541 |
Title of parent work (English): | International journal of foundations of computer science |
Publisher: | World Scientific |
Place of publishing: | Singapore |
Publication type: | Article |
Language: | English |
Year of first publication: | 2012 |
Publication year: | 2012 |
Release date: | 2017/03/26 |
Tag: | Automata systems; cooperating systems; formal languages; theory of computation |
Volume: | 23 |
Issue: | 3 |
Number of pages: | 20 |
First page: | 713 |
Last Page: | 732 |
Organizational units: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik und Computational Science |
Peer review: | Referiert |
Institution name at the time of the publication: | Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik |