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

Abstract

top
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.

How to cite

top

Choudhary, 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
  1. A. O. Buda, Multiprocessor automata. Inform. Proces. Lett.25 (1977) 257–261.  
  2. 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
  3. 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
  4. J. Dassow and V. Mitrana, stack cooperation in multi-stack pushdown automata. J. Comput. Syst. Sci.58 (1999) 611–621.  Zbl0939.68070
  5. J. Dassow, Gh. Paun and G. Rozenberg, Grammar systems, in [9].  
  6. J. Hartmanis, On nondeterminancy in simple computing devices. Acta Inform.1 (1972) 336–344.  Zbl0229.68014
  7. O.H. Ibarra, On two-way multihead automata. J. Comput. Syst. Sci. 7 (1973) 28–36.  Zbl0256.68028
  8. 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
  9. G. Rozenberg, A. Salomaa (eds.), The Handbook of Formal Languages, Springer-Verlag (1997).  

NotesEmbed ?

top

You 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.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.