Robust undecidability of timed and hybrid systems

T.A. Henzinger, J. Raskin, in:, Springer, 2000, pp. 145–159.

Download
No fulltext has been uploaded. References only!

Conference Paper | Published
Author
;
Series Title
LNCS
Abstract
The algorithmic approach to the analysis of timed and hybrid systems is fundamentally limited by undecidability, of universality in the timed case (where all continuous variables are clocks), and of emptiness in the rectangular case (which includes drifting clocks). Traditional proofs of undecidability encode a single Turing computation by a single timed trajectory. These proofs have nurtured the hope that the introduction of “fuzziness” into timed and hybrid models (in the sense that a system cannot distinguish between trajectories that are sufficiently similar) may lead to decidability. We show that this is not the case, by sharpening both fundamental undecidability results. Besides the obvious blow our results deal to the algorithmic method, they also prove that the standard model of timed and hybrid systems, while not “robust” in its definition of trajectory acceptance (which is affected by tiny perturbations in the timing of events), is quite robust in its mathematical properties: the undecidability barriers are not affected by reasonable perturbations of the model.
Publishing Year
Date Published
2000-01-01
Acknowledgement
This research was supported in part by the DARPA (NASA) grant NAG2-1214, the DARPA (Wright-Patterson AFB) grant F33615-C-98-3614, the ARO MURI grant DAAH-04-96-1-0341, and the NSF CAREER award CCR-9501708.
Volume
1790
Page
145 - 159
Conference
HSCC: Hybrid Systems - Computation and Control
IST-REx-ID

Cite this

Henzinger TA, Raskin J. Robust undecidability of timed and hybrid systems. In: Vol 1790. Springer; 2000:145-159. doi:10.1007/3-540-46430-1_15
Henzinger, T. A., & Raskin, J. (2000). Robust undecidability of timed and hybrid systems (Vol. 1790, pp. 145–159). Presented at the HSCC: Hybrid Systems - Computation and Control, Springer. https://doi.org/10.1007/3-540-46430-1_15
Henzinger, Thomas A, and Jean Raskin. “Robust Undecidability of Timed and Hybrid Systems,” 1790:145–59. Springer, 2000. https://doi.org/10.1007/3-540-46430-1_15.
T. A. Henzinger and J. Raskin, “Robust undecidability of timed and hybrid systems,” presented at the HSCC: Hybrid Systems - Computation and Control, 2000, vol. 1790, pp. 145–159.
Henzinger TA, Raskin J. 2000. Robust undecidability of timed and hybrid systems. HSCC: Hybrid Systems - Computation and Control, LNCS, vol. 1790. 145–159.
Henzinger, Thomas A., and Jean Raskin. Robust Undecidability of Timed and Hybrid Systems. Vol. 1790, Springer, 2000, pp. 145–59, doi:10.1007/3-540-46430-1_15.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar