The search result changed since you submitted your search request. Documents might be displayed in a different sort order.
  • search hit 3 of 23
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

Search Google Scholar Statistics
Metadaten
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
Accept ✔
This website uses technically necessary session cookies. By continuing to use the website, you agree to this. You can find our privacy policy here.