Home » Keyword index

bounded tree width


Logic » Finite Model Theory

Complexity of QBF(Bounded Treewidth) ★★

Author(s): Moshe Y. Vardi

Question   What is the computational complexity of QBF(Bounded Treewidth)? Is it PSPACE-complete? In PTIME?

Keywords: bounded tree width; Computational Complexity; FMT12-LesHouches; QBF

Posted by myvardi
updated May 18th, 2012
add new comment
Logic » Finite Model Theory

Monadic second-order logic with cardinality predicates ★★

Author(s): Courcelle

The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:

    \item $ \text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{''} $ \item $ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{''} $

where $ A $ is a fixed recursive set of integers.

Let us fix $ k $ and a closed formula $ F $ in this language.

Conjecture   Is it true that the validity of $ F $ for a graph $ G $ of tree-width at most $ k $ can be tested in polynomial time in the size of $ G $?

Keywords: bounded tree width; cardinality predicates; FMT03-Bedlewo; MSO

Posted by dberwanger
updated May 18th, 2012
add new comment
Syndicate content