## Robust Timed Automata

*Vineet Gupta,
Thomas A. Henzinger,
and Radha Jagadeesan*

We define *robust timed automata*, which are timed automata that
accept all trajectories "robustly": if a robust timed automaton
accepts a trajectory, then it must accept neighboring trajectories
also; and if a robust timed automaton rejects a trajectory, then it
must reject neighboring trajectories also. We show that the emptiness
problem for robust timed automata is still decidable, by modifying the
region construction for timed automata. We then show that, like timed
automata, robust timed automata cannot be determinized. This result
is somewhat unexpected, given that in temporal logic, the removal of
real-time equality constraints is known to lead to a decidable theory
that is closed under all boolean operations.

*Proceedings of the
International Workshop on Hybrid and Real-Time Systems*
(HART),
Lecture Notes in Computer Science 1201,
Springer, 1997, pp. 331-345.

Download inofficial, sometimes updated
PostScript /
PDF document.
© 1997 Springer.