Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-17T00:51:49.134Z Has data issue: false hasContentIssue false

Systems of parallel communicating restartingautomata

Published online by Cambridge University Press:  21 January 2014

Marcel Vollweiler
Affiliation:
Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. vollweiler@theory.informatik.uni-kassel.de,otto@theory.informatik.uni-kassel.de
Friedrich Otto
Affiliation:
Fachbereich Elektrotechnik/Informatik, Universität Kassel, 34109 Kassel, Germany. vollweiler@theory.informatik.uni-kassel.de,otto@theory.informatik.uni-kassel.de

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Several types of systems of parallel communicating restarting automata are introduced andstudied. The main result shows that, for all types of restarting automata X, centralizedsystems of restarting automata of type X have the same computational power asnon-centralized systems of restarting automata of the same type and the same number ofcomponents. This result is proved by a direct simulation. In addition, it is shown thatfor one-way restarting automata without auxiliary symbols, systems of degree at least twoare more powerful than the component automata themselves. Finally, a lower and an upperbound are given for the expressive power of systems of parallel communicating restartingautomata.