Coarse abstractions make Zeno behaviours difficult to detect

Details Coarse abstractions make Zeno behaviours difficult to detect Coarse abstractions make Zeno behaviours difficult to detect

2011-06-09

arxiv.org/abs/1106.1850v1

Computer Science

Logic in Computer Science

CONCUR 2011 - Concurrency Theory, 22nd International Conference

Scientific paper

10.1007/978-3-642-23217-6_7

An infinite run of a timed automaton is Zeno if it spans only a finite amount of time. Such runs are considered unfeasible and hence it is important to detect them, or dually, find runs that are non-Zeno. Over the years important improvements have been obtained in checking reachability properties for timed automata. We show that some of these very efficient optimizations make testing for Zeno runs costly. In particular we show NP-completeness for the LU-extrapolation of Behrmann et al. We analyze the source of this complexity in detail and give general conditions on extrapolation operators that guarantee a (low) polynomial complexity of Zenoness checking. We propose a slight weakening of the LU-extrapolation that satisfies these conditions.

Affiliated with

Also associated with

No associations

Rating

Coarse abstractions make Zeno behaviours difficult to detect 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 Coarse abstractions make Zeno behaviours difficult to detect, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Coarse abstractions make Zeno behaviours difficult to detect will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-580659