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.