Paper Info
Title
The algorithmic analysis of hybrid systems
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.
Year
DOI
Venue
1995
10.1016/0304-3975(94)00202-T
Theor. Comput. Sci.
Keywords
DocType
Volume
hybrid system,linear hybrid system,algorithmic analysis,infinite state space,multidimensional real space,present approximation technique,reachability analysis,state set,analog environment,convex polyhedron,Algorithmic Analysis,Hybrid Systems
Journal
138
Issue
ISSN
Citations 
1
0304-3975
604
PageRank 
References 
Authors
73.89
21
9
Search Limit
100604
Name
Order
Citations
PageRank
Rajeev Alur1172531413.65
Costas Courcoubetis23821467.42
Nicolas Halbwachs33957426.43
Thomas A. Henzinger4148271317.51
Pei-hsin Ho52577305.29
X. Nicollin672794.26
Alfredo Olivero71163159.04
Joseph Sifakis86064814.75
Sergio Yovine93076351.88