Systems of parallel communicating restarting automata

Marcel Vollweiler; Friedrich Otto

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications (2014)

  • Volume: 48, Issue: 1, page 3-22
  • ISSN: 0988-3754

Abstract

top
Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols, systems of degree at least two are more powerful than the component automata themselves. Finally, a lower and an upper bound are given for the expressive power of systems of parallel communicating restarting automata.

How to cite

top

Vollweiler, Marcel, and Otto, Friedrich. "Systems of parallel communicating restarting automata." RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications 48.1 (2014): 3-22. <http://eudml.org/doc/273066>.

@article{Vollweiler2014,
abstract = {Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols, systems of degree at least two are more powerful than the component automata themselves. Finally, a lower and an upper bound are given for the expressive power of systems of parallel communicating restarting automata.},
author = {Vollweiler, Marcel, Otto, Friedrich},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications},
keywords = {parallel communicating system; restarting automaton; language class},
language = {eng},
number = {1},
pages = {3-22},
publisher = {EDP-Sciences},
title = {Systems of parallel communicating restarting automata},
url = {http://eudml.org/doc/273066},
volume = {48},
year = {2014},
}

TY - JOUR
AU - Vollweiler, Marcel
AU - Otto, Friedrich
TI - Systems of parallel communicating restarting automata
JO - RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications
PY - 2014
PB - EDP-Sciences
VL - 48
IS - 1
SP - 3
EP - 22
AB - Several types of systems of parallel communicating restarting automata are introduced and studied. The main result shows that, for all types of restarting automata X, centralized systems of restarting automata of type X have the same computational power as non-centralized systems of restarting automata of the same type and the same number of components. This result is proved by a direct simulation. In addition, it is shown that for one-way restarting automata without auxiliary symbols, systems of degree at least two are more powerful than the component automata themselves. Finally, a lower and an upper bound are given for the expressive power of systems of parallel communicating restarting automata.
LA - eng
KW - parallel communicating system; restarting automaton; language class
UR - http://eudml.org/doc/273066
ER -

References

top
  1. [1] H. Bordihn, M. Kutrib and A. Malcher, On the computational capacity of parallel communicating finite automata, in Developments in Language Theory. In vol. 5257 of Lect. Notes Comput. Sci., edited by M. Ito and M. Toyama. Springer, Berlin (2008) 146–157. Zbl1161.68513MR2490952
  2. [2] E. Csuhaj-Varjú, J. Dassow, J. Kelemen and G. Pãun, Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach Science Publishers, Newark, NJ, USA (1994). Zbl0925.68286MR1475215
  3. [3] E. Csuhaj-Varjú, C. Martín-Vide, V. Mitrana and G. Vaszil, Parallel communicating pushdown automata systems. Int. J. Found. Comput. Sci.11 (2000) 633–650. Zbl0970.68090MR1810040
  4. [4] M. Goehring, PC-systems of restarting automata, in Theorietag Automaten und Formale Sprachen 2009, Technical Report 2009/03, edited by J. Mielke, L. Staiger and R. Winter. Universität Halle-Wittenberg, Institut für Informatik (2009) 26–27. 
  5. [5] J. Hartmanis, On non-determinancy in simple computing devices. Acta Informatica1 (1972) 336–344. Zbl0229.68014MR317582
  6. [6] P. Jančar, F. Mráz, M. Plátek and J. Vogel, Restarting automata, FCT’95, in vol. 965 of Lect. Notes Comput. Sci., edited by H. Reichel. Springer, Berlin (1995) 283–292. MR1459184
  7. [7] 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.68069MR1945313
  8. [8] H. Messerschmidt and F. Otto, Cooperating distributed systems of restarting automata. Int. J. Found. Comput. Sci.18 (2007) 1333–1342. Zbl1183.68347MR2363813
  9. [9] F. Mráz, Lookahead hierarchies of restarting automata. J. Automata, Languages and Combinatorics 6 (2001) 493–506. Zbl1004.68091MR1897057
  10. [10] B. Nagy and F. Otto, CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO: ITA 45 (2011) 413–448. Zbl1250.68172MR2876115
  11. [11] B. Nagy and F. Otto, On CD-systems of stateless deterministic R-automata with window size one. J. Comput. Syst. Sci.78 (2012) 780–806. Zbl1279.68167MR2900034
  12. [12] G. Niemann and F. Otto, Further results on restarting automata, in Words, Languages and Combinatorics, edited by M. Ito and T. Imaoka. World Scientific, Singapore (2003) 352–369. MR2028887
  13. [13] F. Otto, Restarting automata, in Recent Advances in Formal Languages and Applications, vol. 25 of Studies in Computational Intelligence, edited by Z. Ésik, C. Martín-Vide and V. Mitrana. Springer, Berlin (2006) 269–303. Zbl1116.68044
  14. [14] F. Otto, Asynchronous PC Systems of Pushdown Automata, in Language and Automata Theory and Applications. In vol. 7810 of Lect. Notes Comput. Sci., edited by A.-H. Dediu, C. Martín-Vide and B. Truthe. Springer Berlin/Heidelberg (2013) 456–467. Zbl06145890MR3090340
  15. [15] G. Pãun and L. Santean, Parallel communicating grammar systems: the regular case. Analele Universitatii din Bucuresti, Seria matematica-informatica 2 (1989) 55–63. Zbl0749.68048MR1100348
  16. [16] M. Vollweiler, Asynchronous systems of parallel communicating finite automata, in vol. 294 of 5th Workshop on Non-Classical Models of Automata and Appl., edited by S. Bensch, F. Drewes, R. Freund and F. Otto. books@acg.at, Österreichische Computer Gesellschaft, Wien (2013) 243–257. 
  17. [17] M. Vollweiler and F. Otto, Systems of parallel communicating restarting automata, in vol. 290 of 4th Workshop on Non-Classical Models of Automata and Applications, edited by R. Freund, M. Holzer, B. Truthe and U. Ultes-Nitsche. books@acg.at, Österreichische Computer Gesellschaft, Wien (2012) 197–212. Zbl06333639

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.