Geodesic
Systems of parallel communicating restarting automata
RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications, Tome 48 (2014) no. 1, pp. 3-22

Voir la notice de l'article provenant de la source Numdam

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.

DOI : 10.1051/ita/2013046
Classification : 68Q45
Keywords: 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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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://geodesic.mathdoc.fr/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

Cité par Sources :