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.

 gzipped postscript file