Compositional Model Checking of Real Time Systems

Forfattere

  • Francois Laroussinie
  • Kim G. Larsen

DOI:

https://doi.org/10.7146/brics.v2i19.19921

Resumé

A major problem in applying model checking to finite-state systems
is the potential combinatorial explosion of the state space arising from
parallel composition. Solutions of this problem have been attempted for
practical applications using a variety of techniques. Recent work by Andersen
[And95] proposes a very promising compositional model checking
technique, which has experimentally been shown to improve results obtained
using Binary Decision Diagrams.
In this paper we make Andersen's technique applicable to systems described
by networks of timed automata. We present a quotient construction,
which allows timed automata components to be gradually moved from
the network expression into the specification. The intermediate specifications
are kept small using minimization heuristics suggested by Andersen.
The potential of the combined technique is demonstrated using a prototype
implemented in CAML.

Downloads

Publiceret

1995-01-19

Citation/Eksport

Laroussinie, F., & Larsen, K. G. (1995). Compositional Model Checking of Real Time Systems. BRICS Report Series, 2(19). https://doi.org/10.7146/brics.v2i19.19921

Nummer

Nr. 19 (1995): RS-19 Compositional Model Checking of Real Time Systems

Sektion

Artikler

Licens

Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.

    1. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.

  1. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).