An undecidable problem for timed automata

Authors
Citation
A. Puri, An undecidable problem for timed automata, DISCR EVENT, 9(2), 1999, pp. 135-146
Citations number
5
Categorie Soggetti
AI Robotics and Automatic Control
Journal title
DISCRETE EVENT DYNAMIC SYSTEMS-THEORY AND APPLICATIONS
ISSN journal
09246703 → ACNP
Volume
9
Issue
2
Year of publication
1999
Pages
135 - 146
Database
ISI
SICI code
0924-6703(199905)9:2<135:AUPFTA>2.0.ZU;2-0
Abstract
The reachability problem for timed automata is decidable when the coefficie nts in the guards are rational numbers. We show that the reachability probl em is undecidable when the coefficients are chosen from the set {1, root 2} . A consequence of this is that the parameter synthesis problem for timed a utomata with even a single parameter is undecidable. We discuss why such un decidability results arise in timed and hybrid systems, what they mean, and if it is possible to "get around" them.