Paper Info
Title
Product Interval Automata: A Subclass of Timed Automata
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 [4,10] 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 called distributed interval automata.
Year
DOI
Venue
1999
10.1007/3-540-46691-6_5
FSTTCS
Keywords
Field
DocType
language-theoretic term,key restriction,product interval automaton,mazurkiewicz trace,rich theory,interval automaton,product interval automata,clean theory,partial order,partial order reduction technique,timed automata,important consequence,partial order reduction
Discrete mathematics,Quantum finite automata,Automata theory,Continuous spatial automaton,Mobile automaton,Nested word,Computer science,Theoretical computer science,Finite-state machine,Timed automaton,ω-automaton
Conference
ISBN
Citations 
PageRank 
3-540-66836-5
11
0.69
References 
Authors
21
2
Name
Order
Citations
PageRank
Deepak D'souza123917.90
P. S. Thiagarajan21497193.71