Systems of parallel communicating restarting automata

Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany
vollweiler@theory.informatik.uni-kassel.de,otto@theory.informatik.uni-kassel.de

Received: 23 January 2013
Accepted: 11 December 2013

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.