Home » Keyword index

FMT12-LesHouches


Logic » Finite Model Theory

Vertex Cover Integrality Gap ★★

Author(s): Atserias

Conjecture   For every $ \varepsilon > 0 $ there is $ \delta > 0 $ such that, for every large $ n $, there are $ n $-vertex graphs $ G $ and $ H $ such that $ G \equiv_{\delta n}^{\mathrm{C}} H $ and $ \mathrm{vc}(G) \ge (2 - \varepsilon) \cdot \mathrm{vc}(H) $.

Keywords: counting quantifiers; FMT12-LesHouches

Posted by dberwanger
updated October 2nd, 2012
add new comment
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

MSO alternation hierarchy over pictures ★★

Author(s): Grandjean

Question   Is the MSO-alternation hierarchy strict for pictures that are balanced, in the sense that the width and the length are polynomially (or linearly) related.

Keywords: FMT12-LesHouches; MSO, alternation hierarchy; picture languages

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

Order-invariant queries ★★

Author(s): Segoufin

Question  
    \item Does $ {<}\text{-invariant\:FO} = \text{FO} $ hold over graphs of bounded tree-width? \item Is $ {<}\text{-invariant\:FO} $ included in $ \text{MSO} $ over graphs? \item Does $ {<}\text{-invariant\:FO} $ have a 0-1 law? \item Are properties of $ {<}\text{-invariant\:FO} $ Hanf-local? \item Is there a logic (with an effective syntax) that captures $ {<}\text{-invariant\:FO} $?

Keywords: Effective syntax; FMT12-LesHouches; Locality; MSO; Order invariance

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