# 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

top## How 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). Zbl0925.68286
- 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. Zbl0970.68090
- J. Dassow and V. Mitrana, stack cooperation in multi-stack pushdown automata. J. Comput. Syst. Sci.58 (1999) 611–621. Zbl0939.68070
- 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. Zbl0229.68014
- O.H. Ibarra, On two-way multihead automata. J. Comput. Syst. Sci. 7 (1973) 28–36. Zbl0256.68028
- 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. Zbl1066.68069
- G. Rozenberg, A. Salomaa (eds.), The Handbook of Formal Languages, Springer-Verlag (1997).

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.