Undecidability and hierarchy results for parallel communicating finite automata
- Parallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministicParallel communicating finite automata (PCFAs) are systems of several finite state automata which process a common input string in a parallel way and are able to communicate by sending their states upon request. We consider deterministic and nondeterministic variants and distinguish four working modes. It is known that these systems in the most general mode are as powerful as one-way multi-head finite automata. It is additionally known that the number of heads corresponds to the number of automata in PCFAs in a constructive way. Thus, undecidability results as well as results on the hierarchies induced by the number of heads carry over from multi-head finite automata to PCFAs in the most general mode. Here, we complement these undecidability and hierarchy results also for the remaining working modes. In particular, we show that classical decidability questions are not semi-decidable for any type of PCFAs under consideration. Moreover, it is proven that the number of automata in the system induces infinite hierarchies for deterministic and nondeterministic PCFAs in three working modes.…
Author details: | Henning BordihnORCiD, Martin Kutrib, Andreas Malcher |
---|---|
DOI: | https://doi.org/10.1142/S0129054111008891 |
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: | 2011 |
Publication year: | 2011 |
Release date: | 2017/03/26 |
Tag: | Automata systems; cooperating systems; decidability questions; formal languages |
Volume: | 22 |
Issue: | 7 |
Number of pages: | 16 |
First page: | 1577 |
Last Page: | 1592 |
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 |