TY  - JOUR
A1  - Bordihn, Henning
A1  - Kutrib, Martin
A1  - Malcher, Andreas
T1  - On the computational capacity of parallel communicating finite automata
JF  - International journal of foundations of computer science
N2  - 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.
KW  - Automata systems
KW  - cooperating systems
KW  - formal languages
KW  - theory of computation
Y1  - 2012
U6  - https://doi.org/10.1142/S0129054112500062
SN  - 0129-0541
VL  - 23
IS  - 3
SP  - 713
EP  - 732
PB  - World Scientific
CY  - Singapore
ER  - 
TY  - JOUR
A1  - Bordihn, Henning
A1  - Kutrib, Martin
A1  - Malcher, Andreas
T1  - Undecidability and hierarchy results for parallel communicating finite automata
JF  - International journal of foundations of computer science
N2  - 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 deterministic and nondeterministic PCFAs in three working modes.
KW  - Automata systems
KW  - cooperating systems
KW  - formal languages
KW  - decidability questions
Y1  - 2011
U6  - https://doi.org/10.1142/S0129054111008891
SN  - 0129-0541
VL  - 22
IS  - 7
SP  - 1577
EP  - 1592
PB  - World Scientific
CY  - Singapore
ER  -