MSO


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