Using non-convex approximations for efficient analysis of timed automata

Details Using non-convex approximations for efficient analysis of timed automata Using non-convex approximations for efficient analysis of timed automata

2011-10-17

arxiv.org/abs/1110.3704v1

Computer Science

Logic in Computer Science

Extended version of FSTTCS 2011 paper

Scientific paper

10.4230/LIPIcs.FSTTCS.2011.78

The reachability problem for timed automata asks if there exists a path from an initial state to a target state. The standard solution to this problem involves computing the zone graph of the automaton, which in principle could be infinite. In order to make the graph finite, zones are approximated using an extrapolation operator. For reasons of efficiency in current algorithms extrapolation of a zone is always a zone and in particular it is convex. In this paper, we propose to solve the reachability problem without such extrapolation operators. To ensure termination, we provide an efficient algorithm to check if a zone is included in the so called region closure of another. Although theoretically better, closure cannot be used in the standard algorithm since a closure of a zone may not be convex. An additional benefit of the proposed approach is that it permits to calculate approximating parameters on-the-fly during exploration of the zone graph, as opposed to the current methods which do it by a static analysis of the automaton prior to the exploration. This allows for further improvements in the algorithm. Promising experimental results are presented.

Affiliated with

Also associated with

No associations

Rating

Using non-convex approximations for efficient analysis of timed automata 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 Using non-convex approximations for efficient analysis of timed automata, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Using non-convex approximations for efficient analysis of timed automata will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-318758