http://openproblemgarden.org/op/monadic_second_order_logic_with_cardinality_predicates Comments for "Monadic second-order logic with cardinality predicates" en http://openproblemgarden.org/op/monadic_second_order_logic_with_cardinality_predicates <table cellspacing="10"> <tr> <td> Author(s): <a href="/category/courcelle_bruno">Courcelle</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> <p>The problem concerns the extension of Monadic Second Order Logic (over a binary relation representing the edge relation) with the following atomic formulas:<br /> <ul class="itemize"> \item <img class="teximage" src="/files/tex/4e2db7139204fa27f423952041df6049f00cf030.png" alt="$ \text{``}\,\mathrm{Card}(X) = \mathrm{Card}(Y)\,\text{&#039;&#039;} $" /> \item <img class="teximage" src="/files/tex/3a5b94d5bb93d9aefdfdf917ad8c8535a0328199.png" alt="$ \text{``}\,\mathrm{Card}(X) \text{ belongs to } A\,\text{&#039;&#039;} $" /> </ul> <p> where <img class="teximage" src="/files/tex/7a8d9782350e8eb5a84c149576d83160492cbdd3.png" alt="$ A $" /> is a fixed recursive set of integers.</p> <p>Let us fix <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> and a closed formula <img class="teximage" src="/files/tex/bfff269cc7df9bdb7c57d8b6a2a74020d114f24d.png" alt="$ F $" /> in this language.</p> <div class="envtheorem"><b>Conjecture</b>&nbsp;&nbsp; Is it true that the validity of <img class="teximage" src="/files/tex/bfff269cc7df9bdb7c57d8b6a2a74020d114f24d.png" alt="$ F $" /> for a graph <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" /> of tree-width at most <img class="teximage" src="/files/tex/c450c3185f7285cfa0b88d3a903c54f7df601201.png" alt="$ k $" /> can be tested in polynomial time in the size of <img class="teximage" src="/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png" alt="$ G $" />? </div> </tr></td> </table> </td> </tr> </table> Courcelle, Bruno bounded tree width cardinality predicates FMT03-Bedlewo MSO Logic Finite Model Theory http://openproblemgarden.org/op/monadic_second_order_logic_with_cardinality_predicates#comment Fri, 18 May 2012 10:42:25 +0200 dberwanger 37440 at http://openproblemgarden.org