Home » Subject » Logic » Finite Model Theory

Monadic second-order logic with cardinality predicates

Importance: Medium ✭✭
Author(s): Courcelle, Bruno
Subject: Logic
» Finite Model Theory
Keywords: bounded tree width
cardinality predicates
FMT03-Bedlewo
MSO
Recomm. for undergrads: no
Posted by: dberwanger
on: May 18th, 2012

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 $?

Bibliography



* indicates original appearance(s) of problem.
add new comment