2026-07-22T11:26:24Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:15737 2024-03-06T10:56:04Z ddc:004 open_access

MSO Undecidability for Hereditary Classes of Unbounded Clique Width Dawar, Anuj Sankaran, Abhisekh clique width Seese’s conjecture antichain MSO interpretation grid Seese’s conjecture for finite graphs states that monadic second-order logic (MSO) is undecidable on all graph classes of unbounded clique-width. We show that to establish this it would suffice to show that grids of unbounded size can be interpreted in two families of graph classes: minimal hereditary classes of unbounded clique-width; and antichains of unbounded clique-width under the induced subgraph relation. We explore all the currently known classes of the former category and establish that grids of unbounded size can indeed be interpreted in them. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Anuj Dawar and Abhisekh Sankaran 2022 Is Part Of LIPIcs, Volume 216, 30th EACSL Annual Conference on Computer Science Logic (CSL 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CSL.2022.17 urn:nbn:de:0030-drops-157373 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CSL.2022.17 eng https://creativecommons.org/licenses/by/4.0/legalcode