Distributed Time-Asynchronous Automata.

Authors :: Hutchison, David
Kanade, Takeo
Kittler, Josef
Kleinberg, Jon M.
Mattern, Friedemann
Mitchell, John C.
Naor, Moni
Nierstrasz, Oscar
Pandu Rangan, C.
Steffen, Bernhard
Sudan, Madhu
Terzopoulos, Demetri
Tygar, Doug
Vardi, Moshe Y.
Weikum, Gerhard
Jones, Cliff B.
Liu, Zhiming
Woodcock, Jim
Dima, Cătălin
Lanotte, Ruggero
Source :: Theoretical Aspects of Computing - ICTAC 2007; 2007, p185-200, 16p
Publication Year :: 2007
Abstract: We show that the class of distributed time-asynchronous automata is more expressive than timed automata, has a decidable emptiness problem, is closed under union, concatenation, star, shuffle and renaming, but not under intersection. The closure results are obtained by showing that distributed time-asynchronous automata are equivalent with a subclass of shuffle regular expressions and its related class of stopwatch automata. [ABSTRACT FROM AUTHOR]