Returning and non-returning parallel communicating finite automata are equivalent
Ashish Choudhary; Kamala Krithivasan; Victor Mitrana
RAIRO - Theoretical Informatics and Applications (2007)
- Volume: 41, Issue: 2, page 137-145
- ISSN: 0988-3754
Access Full Article
top
Abstract
topHow to cite
topChoudhary, Ashish, Krithivasan, Kamala, and Mitrana, Victor. "Returning and non-returning parallel communicating finite automata are equivalent." RAIRO - Theoretical Informatics and Applications 41.2 (2007): 137-145. <http://eudml.org/doc/250068>.
@article{Choudhary2007,
abstract = {
A parallel communicating automata system consists of several automata working independently in parallel and
communicating with each other by request with the aim of recognizing a word.
Rather surprisingly, returning parallel communicating finite automata systems are equivalent
to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata.
Some open problems are finally formulated.
},
author = {Choudhary, Ashish, Krithivasan, Kamala, Mitrana, Victor},
journal = {RAIRO - Theoretical Informatics and Applications},
keywords = {Formal languages; parallel communicating finite automata system; multihead finite automaton; computational power; multihead finite automata},
language = {eng},
month = {7},
number = {2},
pages = {137-145},
publisher = {EDP Sciences},
title = {Returning and non-returning parallel communicating finite automata are equivalent},
url = {http://eudml.org/doc/250068},
volume = {41},
year = {2007},
}
TY - JOUR
AU - Choudhary, Ashish
AU - Krithivasan, Kamala
AU - Mitrana, Victor
TI - Returning and non-returning parallel communicating finite automata are equivalent
JO - RAIRO - Theoretical Informatics and Applications
DA - 2007/7//
PB - EDP Sciences
VL - 41
IS - 2
SP - 137
EP - 145
AB -
A parallel communicating automata system consists of several automata working independently in parallel and
communicating with each other by request with the aim of recognizing a word.
Rather surprisingly, returning parallel communicating finite automata systems are equivalent
to the non-returning variants. We show this result by proving the equivalence of both with multihead finite automata.
Some open problems are finally formulated.
LA - eng
KW - Formal languages; parallel communicating finite automata system; multihead finite automaton; computational power; multihead finite automata
UR - http://eudml.org/doc/250068
ER -
References
top- A. O. Buda, Multiprocessor automata. Inform. Proces. Lett.25 (1977) 257–261.
- E. Csuhaj-Varju, J. Dassow, J. Kelemen and Gh. Paun, Grammar Systems. A grammatical approach to distribution and cooperation. Gordon and Breach (1994).
- E. Csuhaj-Varju, C. Martin-Vide, V. Mitrana and G. Vaszil, Parallel communicating pushdown automata systems. Int. J. Found. Comput. Sci.11 (2000) 633–650.
- J. Dassow and V. Mitrana, stack cooperation in multi-stack pushdown automata. J. Comput. Syst. Sci.58 (1999) 611–621.
- J. Dassow, Gh. Paun and G. Rozenberg, Grammar systems, in [9].
- J. Hartmanis, On nondeterminancy in simple computing devices. Acta Inform.1 (1972) 336–344.
- O.H. Ibarra, On two-way multihead automata. J. Comput. Syst. Sci. 7 (1973) 28–36.
- C. Martín-Vide, A. Mateescu and V. Mitrana, Parallel finite automata systems communicating by states. Int. J. Found. Comput. Sci.13 (2002) 733–749.
- G. Rozenberg, A. Salomaa (eds.), The Handbook of Formal Languages, Springer-Verlag (1997).
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.