Home » Keyword index

Order invariance


Logic » Finite Model Theory

Order-invariant queries ★★

Author(s): Segoufin

Question  
  1. Does $ {<}\text{-invariant\:FO} = \text{FO} $ hold over graphs of bounded tree-width?
  2. Is $ {<}\text{-invariant\:FO} $ included in $ \text{MSO} $ over graphs?
  3. Does $ {<}\text{-invariant\:FO} $ have a 0-1 law?
  4. Are properties of $ {<}\text{-invariant\:FO} $ Hanf-local?
  5. 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