The algorithmic analysis of hybrid systems

R. Alur, C. Courcoubetis, N. Halbwachs, T.A. Henzinger, P. Ho, X. Nicollin, A. Olivero, J. Sifakis, S. Yovine, Theoretical Computer Science 138 (1995) 3–34.

Download
No fulltext has been uploaded. References only!

Journal Article | Published
Author
; ; ; ; ; ; ; ;
Abstract
We present a general framework for the formal specification and algorithmic analysis of hybrid systems. A hybrid system consists of a discrete program with an analog environment. We model hybrid systems as finite automata equipped with variables that evolve continuously with time according to dynamical laws. For verification purposes, we restrict ourselves to linear hybrid systems, where all variables follow piecewise-linear trajectories. We provide decidability and undecidability results for classes of linear hybrid systems, and we show that standard program-analysis techniques can be adapted to linear hybrid systems. In particular, we consider symbolic model-checking and minimization procedures that are based on the reachability analysis of an infinite state space. The procedures iteratively compute state sets that are definable as unions of convex polyhedra in multidimensional real space. We also present approximation techniques for dealing with systems for which the iterative procedures do not converge.
Publishing Year
Date Published
1995-02-06
Journal Title
Theoretical Computer Science
Volume
138
Issue
1
Page
3 - 34
IST-REx-ID

Cite this

Alur R, Courcoubetis C, Halbwachs N, et al. The algorithmic analysis of hybrid systems. Theoretical Computer Science. 1995;138(1):3-34. doi:10.1016/0304-3975(94)00202-T
Alur, R., Courcoubetis, C., Halbwachs, N., Henzinger, T. A., Ho, P., Nicollin, X., … Yovine, S. (1995). The algorithmic analysis of hybrid systems. Theoretical Computer Science, 138(1), 3–34. https://doi.org/10.1016/0304-3975(94)00202-T
Alur, Rajeev, Costas Courcoubetis, Nicolas Halbwachs, Thomas A Henzinger, Pei Ho, Xavier Nicollin, Alfredo Olivero, Joseph Sifakis, and Sergio Yovine. “The Algorithmic Analysis of Hybrid Systems.” Theoretical Computer Science 138, no. 1 (1995): 3–34. https://doi.org/10.1016/0304-3975(94)00202-T.
R. Alur et al., “The algorithmic analysis of hybrid systems,” Theoretical Computer Science, vol. 138, no. 1, pp. 3–34, 1995.
Alur R, Courcoubetis C, Halbwachs N, Henzinger TA, Ho P, Nicollin X, Olivero A, Sifakis J, Yovine S. 1995. The algorithmic analysis of hybrid systems. Theoretical Computer Science. 138(1), 3–34.
Alur, Rajeev, et al. “The Algorithmic Analysis of Hybrid Systems.” Theoretical Computer Science, vol. 138, no. 1, Elsevier, 1995, pp. 3–34, doi:10.1016/0304-3975(94)00202-T.

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar