• search hit 54 of 590
Back to Result List

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.

Export metadata

Additional Services

Share in Twitter Search Google Scholar Statistics
Metadaten
Author:Henning Bordihn, Martin Kutrib, Andreas Malcher
DOI:https://doi.org/10.1142/S0129054112500062
ISSN:0129-0541 (print)
Parent Title (English):International journal of foundations of computer science
Publisher:World Scientific
Place of publication:Singapore
Document Type:Article
Language:English
Year of first Publication:2012
Year of Completion:2012
Release Date:2017/03/26
Tag:Automata systems; cooperating systems; formal languages; theory of computation
Volume:23
Issue:3
Pagenumber: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 publication:Mathematisch-Naturwissenschaftliche Fakultät / Institut für Informatik