Skip to Main content Skip to Navigation
Conference papers

Hybrid Acceleration using Real Vector Automata

Abstract : This paper addresses the problem of computing an exact and effective representation of the set of reachable configurations of a linear hybrid automaton. Our solution is based on accelerating the state-space exploration by computing symbolically the repeated effect of cycles in the automaton control graph. The computed sets of configurations are represented by Real Vector Automata (RVA), the expressive power of which is beyond that of the first-order additive theory of reals and integers. This approach makes it possible to compute in finite time sets of configurations that cannot be expressed as finite unions of convex sets. The main technical contributions of the paper consist in a powerful sufficient criterion for checking whether a hybrid transformation (i.e., with both discrete and continuous features) can be accelerated, as well as an algorithm for applying such an accelerated transformation on RVA. Our results have been implemented and successfully applied to several case studies, including the well-known leaking gas burner, and a simple communication protocol with timers.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00335915
Contributor : Frédéric Herbreteau <>
Submitted on : Friday, October 31, 2008 - 12:13:55 PM
Last modification on : Thursday, January 11, 2018 - 6:20:16 AM
Long-term archiving on: : Monday, June 7, 2010 - 7:56:00 PM

File

cav47.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00335915, version 1

Collections

Citation

Bernard Boigelot, Frédéric Herbreteau, Sébastien Jodogne. Hybrid Acceleration using Real Vector Automata. Computer Aided Verification, 15th International Conference, Jul 2003, Boulder, CO, United States. pp.193-205. ⟨inria-00335915⟩

Share

Metrics

Record views

414

Files downloads

217