Paper published in a journal (Scientific congresses and symposiums)
The power of hybrid acceleration
Boigelot, Bernard; Herbreteau, Frédéric
2006In Lecture Notes in Computer Science, 4144, p. 438-451
Peer reviewed
 

Files


Full Text
BH06.pdf
Author postprint (223.54 kB)
Download

The original publication is available at www.springerlink.com


All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
hybrid systems; acceleration; symbolic state-space exploration
Abstract :
[en] This paper addresses the problem of computing symbolically the set of reachable configurations of a linear hybrid automaton. A solution proposed in earlier work consists in exploring the reachable configurations using an acceleration operator for computing the iterated effect of selected control cycles. Unfortunately, this method imposes a periodicity requirement on the data transformations labeling these cycles, that is not always satisfied in practice. This happens in particular with the important subclass of timed automata, even though it is known that the paths of such automata have a periodic behavior. The goal of this paper is to broaden substantially the applicability of hybrid acceleration. This is done by introducing powerful reduction rules, aimed at translating hybrid data transformations into equivalent ones that satisfy the periodicity criterion. In particular, we show that these rules always succeed in the case of timed automata. This makes it possible to compute an exact symbolic representation of the set of reachable configurations of a linear hybrid automaton, with a guarantee of termination over the subclass of timed automata. Compared to other known solutions to this problem, our method is simpler, and applicable to a much larger class of systems.
Disciplines :
Computer science
Author, co-author :
Boigelot, Bernard  ;  Université de Liège - ULiège > Dép. d'électric., électron. et informat. (Inst.Montefiore) > Informatique
Herbreteau, Frédéric;  Laboratoire Bordelais de Recherche en Informatique (LaBRI)
Language :
English
Title :
The power of hybrid acceleration
Publication date :
2006
Event name :
18th International Conferencence on Computer-Aided Verification
Event place :
Seattle, WA, United States
Event date :
August 2006
Audience :
International
Journal title :
Lecture Notes in Computer Science
ISSN :
0302-9743
eISSN :
1611-3349
Publisher :
Springer-Verlag, Berlin Heidelberg, Germany
Volume :
4144
Pages :
438-451
Peer reviewed :
Peer reviewed
Funders :
Project "Persée" of the ACI "Securité informatique" of the French Ministry of Scientific Research
Available on ORBi :
since 05 January 2010

Statistics


Number of views
87 (11 by ULiège)
Number of downloads
133 (5 by ULiège)

Scopus citations®
 
15
Scopus citations®
without self-citations
13
OpenCitations
 
12

Bibliography


Similar publications



Contact ORBi