SMT-based Induction Methods for Timed Systems

Details SMT-based Induction Methods for Timed Systems SMT-based Induction Methods for Timed Systems

2012-04-25

arxiv.org/abs/1204.5639v1

Computer Science

Logic in Computer Science

Scientific paper

Modeling time related aspects is important in many applications of verification methods. For precise results, it is necessary to interpret time as a dense domain, e.g. using timed automata as a formalism, even though the system's resulting infinite state space is challenging for verification methods. Furthermore, fully symbolic treatment of both timing related and non-timing related elements of the state space seems to offer an attractive approach to model checking timed systems with a large amount of non-determinism. This paper presents an SMT-based timed system extension to the IC3 algorithm, a SAT-based novel, highly efficient, complete verification method for untimed systems. Handling of the infinite state spaces of timed system in the extended IC3 algorithm is based on suitably adapting the well-known region abstraction for timed systems. Additionally, $k$-induction, another symbolic verification method for discrete time systems, is extended in a similar fashion to support timed systems. Both new methods are evaluated and experimentally compared to a booleanization-based verification approach that uses the original discrete time IC3 algorithm.

Affiliated with

Also associated with

No associations

Rating

SMT-based Induction Methods for Timed Systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with SMT-based Induction Methods for Timed Systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and SMT-based Induction Methods for Timed Systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-137907