Journal article

Publication year: 2012

Pages: 713-732

Journal: International Journal of Foundations of Computer Science

Volume number: 23

Issue number: 3

ISSN: 0129-0541

DOI Link: https://doi.org/10.1142/S0129054112500062

Publisher: World Scientific Publishing

Abstract: 
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.

Harvard Citation style: Bordihn, H., Kutrib, M. and Malcher, A. (2012) ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA, International Journal of Foundations of Computer Science, 23(3), pp. 713-732. https://doi.org/10.1142/S0129054112500062

APA Citation style: Bordihn, H., Kutrib, M., & Malcher, A. (2012). ON THE COMPUTATIONAL CAPACITY OF PARALLEL COMMUNICATING FINITE AUTOMATA. International Journal of Foundations of Computer Science. 23(3), 713-732. https://doi.org/10.1142/S0129054112500062