Antichains for the Automata-Based Approach to Model-Checking

Details Antichains for the Automata-Based Approach to Model-Checking Antichains for the Automata-Based Approach to Model-Checking

2009-02-23

arxiv.org/abs/0902.3958v2

LMCS 5 (1:5) 2009

Computer Science

Logic in Computer Science

Scientific paper

10.2168/LMCS-5(1:5)2009

We propose and evaluate antichain algorithms to solve the universality and language inclusion problems for nondeterministic Buechi automata, and the emptiness problem for alternating Buechi automata. To obtain those algorithms, we establish the existence of simulation pre-orders that can be exploited to efficiently evaluate fixed points on the automata defined during the complementation step (that we keep implicit in our approach). We evaluate the performance of the algorithm to check the universality of Buechi automata using the random automaton model recently proposed by Tabakov and Vardi. We show that on the difficult instances of this probabilistic model, our algorithm outperforms the standard ones by several orders of magnitude.

Affiliated with

Also associated with

No associations

Rating

Antichains for the Automata-Based Approach to Model-Checking 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 Antichains for the Automata-Based Approach to Model-Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Antichains for the Automata-Based Approach to Model-Checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-584933