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.
Mots-clés : parallel communicating system, restarting automaton, language class
@article{ITA_2014__48_1_3_0,
author = {Vollweiler, Marcel and Otto, Friedrich},
title = {Systems of parallel communicating restarting automata},
journal = {RAIRO - Theoretical Informatics and Applications - Informatique Th\'eorique et Applications},
pages = {3--22},
publisher = {EDP-Sciences},
volume = {48},
number = {1},
year = {2014},
doi = {10.1051/ita/2013046},
mrnumber = {3195786},
language = {en},
url = {http://archive.numdam.org/articles/10.1051/ita/2013046/}
}
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 SP - 3 EP - 22 VL - 48 IS - 1 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/ita/2013046/ DO - 10.1051/ita/2013046 LA - en ID - ITA_2014__48_1_3_0 ER -
%0 Journal Article %A Vollweiler, Marcel %A Otto, Friedrich %T Systems of parallel communicating restarting automata %J RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications %D 2014 %P 3-22 %V 48 %N 1 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/ita/2013046/ %R 10.1051/ita/2013046 %G en %F ITA_2014__48_1_3_0
Vollweiler, Marcel; Otto, Friedrich. Systems of parallel communicating restarting automata. RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 3-22. doi : 10.1051/ita/2013046. http://archive.numdam.org/articles/10.1051/ita/2013046/
[1] , and , 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. | MR | Zbl
[2] , , and , Grammar Systems: A Grammatical Approach to Distribution and Cooperation. Gordon and Breach Science Publishers, Newark, NJ, USA (1994). | MR | Zbl
[3] , , and , Parallel communicating pushdown automata systems. Int. J. Found. Comput. Sci. 11 (2000) 633-650. | MR | Zbl
[4] , 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] , On non-determinancy in simple computing devices. Acta Informatica 1 (1972) 336-344. | MR | Zbl
[6] , , and , Restarting automata, FCT'95, in vol. 965 of Lect. Notes Comput. Sci., edited by H. Reichel. Springer, Berlin (1995) 283-292. | MR
[7] , and , Parallel finite automata systems communicating by states. Int. J. Found. Comput. Sci. 13 (2002) 733-749. | MR | Zbl
[8] and , Cooperating distributed systems of restarting automata. Int. J. Found. Comput. Sci. 18 (2007) 1333-1342. | MR | Zbl
[9] , Lookahead hierarchies of restarting automata. J. Automata, Languages and Combinatorics 6 (2001) 493-506. | MR | Zbl
[10] and , CD-systems of stateless deterministic R(1)-automata governed by an external pushdown store. RAIRO: ITA 45 (2011) 413-448. | Numdam | MR | Zbl
[11] and , On CD-systems of stateless deterministic R-automata with window size one. J. Comput. Syst. Sci. 78 (2012) 780-806. | MR | Zbl
[12] and , Further results on restarting automata, in Words, Languages and Combinatorics, edited by M. Ito and T. Imaoka. World Scientific, Singapore (2003) 352-369. | MR
[13] , 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. | Zbl
[14] , 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. | MR
[15] and , Parallel communicating grammar systems: the regular case. Analele Universitatii din Bucuresti, Seria matematica-informatica 2 (1989) 55-63. | MR | Zbl
[16] , 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] and , 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.
Cité par Sources :
