Anuj Puri
Bell Labs
Dynamical Properties of Timed Automata
- Room 2C-542
- December 11, 1997 at 12:30 PM
Abstract:
In this talk I will discuss the verification problem for timed automata. A
timed automaton is an automaton coupled with a finite number of continuous
clocks. The simplest verification problem is the reachability question ---
whether some undesirable states of the timed automaton are reachable
from the initial state. I will review the work of Alur and Dill and show
that this standard method of solving the reachability problem is not
correct when the clocks drift even by a very small amount. I will then present
a new formulation of the reachability problem which takes the drifting clocks
into account. I will present an algorithm to solve the new problem and provide
an outline for its proof of correctness. To prove the correctness of
our algorithm, we will need to understand the dynamics of timed automata.
I will end with some open issues.