Better abstractions for timed automata

Details Better abstractions for timed automata Better abstractions for timed automata

2011-10-17

arxiv.org/abs/1110.3705v3

Computer Science

Logic in Computer Science

Extended version

Scientific paper

We consider the reachability problem for timed automata. A standard solution to this problem involves computing a search tree whose nodes are abstractions of zones. These abstractions preserve underlying simulation relations on the state space of the automaton. For both effectiveness and efficiency reasons, they are parametrized by the maximal lower and upper bounds (LU-bounds) occurring in the guards of the automaton. We consider the aLU abstraction defined by Behrmann et al. Since this abstraction can potentially yield non-convex sets, it has not been used in implementations. We prove that aLU abstraction is the biggest abstraction with respect to LU-bounds that is sound and complete for reachability. We also provide an efficient technique to use the aLU abstraction to solve the reachability problem.

Affiliated with

Also associated with

No associations

Rating

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

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-318763