Approximate reachability analysis of timed automata
Author:
- 23 December 2002
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 10528725,p. 52-61
Abstract
A promising approach to formal verification of real-time systems is to use timed automata to model systems, and then to check whether certain "unsafe" states are reachable. Although theoretically appealing, this approach has significant practical problems because it requires expensive computation of reachable states. Fortunately computing a superset of reachable states is sometimes much cheaper. Replacing the set of reachable states with its superset is a conservative approximation, in the sense that it can occasionally cause a correct system to be declared incorrect, but can never cause an incorrect system to be declared correct. We propose two algorithms for computing a superset of reachable states of a timed automaton. Both algorithms involve only manipulation of Boolean functions, which are used to represent both sets of discrete state components and timing information. The algorithms offer different trade-offs between accuracy of approximation and efficiency of computation. Initial experimental results show that they are competitive with the best published results, but that further improvements are necessary to scale up to realistic systems.Keywords
This publication has 12 references indexed in Scilit:
- An implementation of three algorithms for timing verification based on automata emptiness2003
- Symbolic model checking for real-time systems2003
- Formal verification of the PATHO real-time operating system2002
- Compositional and symbolic model-checking of real-time systems2002
- HSIS1994
- Iterative Algorithms For Formal Verification Of Embedded Real-time Systems1994
- Symbolic Model Checking1993
- Spectral transforms for large boolean functions with applications to technology mapping1993
- Compiling real-time specifications into extended automataIEEE Transactions on Software Engineering, 1992
- Symbolic model checking: 1020 States and beyondInformation and Computation, 1992