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)
*

**Abstract**
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*).