Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking

Details Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking

2011-06-28

arxiv.org/abs/1106.5700v1

Computer Science

Logic in Computer Science

Extended version of the paper titled "Self-loop aggregation product - a new hybrid approach to on-the-fly LTL model checking"

Scientific paper

We present two new hybrid techniques that replace the synchronized product used in the automata-theoretic approach for LTL model checking. The proposed products are explicit graphs of aggregates (symbolic sets of states) that can be interpreted as B\"uchi automata. These hybrid approaches allow on the one hand to use classical emptiness-check algorithms and build the graph on-the-fly, and on the other hand, to have a compact encoding of the state space thanks to the symbolic representation of the aggregates. The Symbolic Observation Product assumes a globally stuttering property (e.g., LTL \ X) to aggregate states. The Self-Loop Aggregation Product} does not require the property to be globally stuttering (i.e., it can tackle full LTL), but dynamically detects and exploits a form of stuttering where possible. Our experiments show that these two variants, while incomparable with each other, can outperform other existing approaches.

Affiliated with

Also associated with

No associations

Rating

Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL 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 Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Combining Explicit and Symbolic Approaches for Better On-the-Fly LTL Model Checking will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-41715