Abstract
Extended Timed Automata (XTA) is a widely used formalism to show the correctness of industrial applications. The decidability results and current extrapolations for XTA are based on constants in the automaton. However, in the case of XTA such bounds depend on integer variables or variable expressions. Since computing such bounds can be as expensive as the verification task, tools such as Uppaal over-approximate the bounds by values given in the type definitions. These values are excessively large and can yield huge state spaces. In this paper we outline a targeted static analysis to efficiently over-approximate location based invariants (and thereby ranges) of integer variables. We have implemented our analysis in Uppaal where the new tighter bounds are available to all currently implemented extrapolation operations. Our experiments show an exponential reduction in the state space of several models. In addition, the computation overhead introduced by the integer static analysis is negligible.
Originalsprog | Engelsk |
---|---|
Titel | Formal Modeling and Analysis of Timed Systems - 19th International Conference, FORMATS 2021, Proceedings |
Redaktører | Catalin Dima, Mahsa Shirmohammadi |
Antal sider | 16 |
Forlag | Springer |
Publikationsdato | 2021 |
Sider | 84-99 |
ISBN (Trykt) | 9783030850364 |
DOI | |
Status | Udgivet - 2021 |
Begivenhed | 19th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2021 - Virtual, Online Varighed: 24 aug. 2021 → 26 aug. 2021 |
Konference
Konference | 19th International Conference on Formal Modeling and Analysis of Timed Systems, FORMATS 2021 |
---|---|
By | Virtual, Online |
Periode | 24/08/2021 → 26/08/2021 |
Navn | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|
Vol/bind | 12860 LNCS |
ISSN | 0302-9743 |
Bibliografisk note
Publisher Copyright:© 2021, Springer Nature Switzerland AG.