Product Interval Automata: A Subclass of Timed Automata

Product Interval Automata: A Subclass of Timed Automata

D. D'Souza and P. S. Thiagarajan

Proc. 19th FSTTCS, Chennai (1999)


We identify a subclass of timed automata and develop its theory. These automata, called product interval automata, consist of a network of timed agents. The key restriction is that there is just one clock for each agent and the way the clocks are read and reset is determined by the distribution of shared actions across the agents. We show that the resulting automata admit a clean theory in both logical and language theoretic terms. It turns out that the study of these timed automata can exploit the rich theory of partial orders known as Mazurkiewicz traces. An important consequence is that the partial order reduction techniques being developed for timed automata [BJLW98, M99] can be readily applied to the verification tasks associated with our automata. Indeed we expect this to be the case even for the extension of product interval automata that we consider called distributed interval automata.

Available as a gzipped dvi file (23 K) or gzipped postscript file (82 K).