Skip to main content


eCommons@Cornell >
College of Engineering >
Computer Science >
Computer Science Technical Reports >

Please use this identifier to cite or link to this item:
Title: The Algorithmic Analysis of Hybrid Systems
Authors: Alur, Rajeev
Courcoubetis, Costas
Halbwachs, Nicolas
Henzinger, Thomas A.
Ho, Pei-Hsin
Nicollin, Xavier
Olivero, Alfredo
Sifakis, Joseph
Yovine, Sergio
Keywords: computer science
technical report
Issue Date: Oct-1994
Publisher: Cornell University
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.
Appears in Collections:Computer Science Technical Reports

Files in This Item:

File Description SizeFormat
94-1451.pdf317.12 kBAdobe PDFView/Open
94-1451.ps334.49 kBPostscriptView/Open

Refworks Export

Items in eCommons are protected by copyright, with all rights reserved, unless otherwise indicated.


© 2014 Cornell University Library Contact Us