Skip to main content

1999 | OriginalPaper | Buchkapitel

Efficient Verification of Timed Automata Using Dense and Discrete Time Semantics

verfasst von : Marius Bozga, Oded Maler, Stavros Tripakis

Erschienen in: Correct Hardware Design and Verification Methods

Verlag: Springer Berlin Heidelberg

Aktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.

search-config
loading …

In this paper we argue that the semantic issues of discrete vs. dense time should be separated as much as possible from the pragmatics of state-space representation. Contrary to some misconceptions, the discrete semantics is not inherently bound to use state-explosive techniques any more than the dense one. In fact, discrete timed automata can be analyzed using any representation scheme (such as DBM) used for dense time, and in addition can benefit from enumerative and symbolic techniques (such as BDDs) which are not naturally applicable to dense time. DBMs, on the other hand, can still be used more efficiently by taking into account the activity of clocks, to eliminate redundancy. To support these claims we report experimental results obtained using an extension of Kronos with BDDs and variable-dimension DBMs where we verified the asynchronous chip STARI, a FIFO buffer which provides for skew-tolerant communication between two synchronous systems. Using discrete time and BDDs we were able to prove correctness of a STARI implementation with 18 stages (55 clocks), better than what has been achieved using other techniques. The verification results carry over to the dense semantics.Using variable-dimension DBMs we have managed to verify STARI for up to 8 stages (27 clocks). In fact, our analysis shows that at most one third of the clocks are active at any reachable state, and about one fourth of the clocks are active in 90% of the reachable states.

Metadaten
Titel
Efficient Verification of Timed Automata Using Dense and Discrete Time Semantics
verfasst von
Marius Bozga
Oded Maler
Stavros Tripakis
Copyright-Jahr
1999
Verlag
Springer Berlin Heidelberg
DOI
https://doi.org/10.1007/3-540-48153-2_11