Distributed real-time automata

In this paper we build on the suggestion to synchronizations of real-time automata, i.e. tuples of real-time automata that work on their own tape but their transitions are taken synchronously. Decidability of the emptiness problem follows from the fact that this is a subclass of timed automata. We then show that the automata are too powerful, being able to capture a language whose complement Alur and Dill mentioned in their TCS paper not to be accepted by any timed automaton. Hence they are not closed under complementation. We then restrict our attention to a subclass of so-called stuttering-free distributed real-time automata and show that this class is closed under complementation.

C. Martin-Vide and V.
Mitrana (eds.), Grammars and Automata
for String Processing: From Mathematics and
Computer Science to Biology, and Back: Essays in Honour of Gheorghe
Paun.
Topics in Computer Mathematics 9 Taylor and Francis 2003, ISBN
0415298857, *pages 131-140, 2001.*