Courcelle's Theorem - A Game-Theoretic Approach

Details Courcelle's Theorem - A Game-Theoretic Approach Courcelle's Theorem - A Game-Theoretic Approach

2011-04-19

arxiv.org/abs/1104.3905v1

Computer Science

Data Structures and Algorithms

submitted

Scientific paper

Courcelle's Theorem states that every problem definable in Monadic Second-Order logic can be solved in linear time on structures of bounded treewidth, for example, by constructing a tree automaton that recognizes or rejects a tree decomposition of the structure. Existing, optimized software like the MONA tool can be used to build the corresponding tree automata, which for bounded treewidth are of constant size. Unfortunately, the constants involved can become extremely large - every quantifier alternation requires a power set construction for the automaton. Here, the required space can become a problem in practical applications. In this paper, we present a novel, direct approach based on model checking games, which avoids the expensive power set construction. Experiments with an implementation are promising, and we can solve problems on graphs where the automata-theoretic approach fails in practice.

Affiliated with

Also associated with

No associations

Rating

Courcelle's Theorem - A Game-Theoretic Approach 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 Courcelle's Theorem - A Game-Theoretic Approach, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Courcelle's Theorem - A Game-Theoretic Approach will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-431717