License: 
Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CSL.2022.17
URN: urn:nbn:de:0030-drops-157373
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/15737/
Dawar, Anuj ;
Sankaran, Abhisekh
MSO Undecidability for Hereditary Classes of Unbounded Clique Width
Abstract
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.
BibTeX - Entry
@InProceedings{dawar_et_al:LIPIcs.CSL.2022.17,
author = {Dawar, Anuj and Sankaran, Abhisekh},
title = {{MSO Undecidability for Hereditary Classes of Unbounded Clique Width}},
booktitle = {30th EACSL Annual Conference on Computer Science Logic (CSL 2022)},
pages = {17:1--17:17},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-218-1},
ISSN = {1868-8969},
year = {2022},
volume = {216},
editor = {Manea, Florin and Simpson, Alex},
publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15737},
URN = {urn:nbn:de:0030-drops-157373},
doi = {10.4230/LIPIcs.CSL.2022.17},
annote = {Keywords: clique width, Seese’s conjecture, antichain, MSO interpretation, grid}
}
|
Keywords: |
|
clique width, Seese’s conjecture, antichain, MSO interpretation, grid |
|
Collection: |
|
30th EACSL Annual Conference on Computer Science Logic (CSL 2022) |
|
Issue Date: |
|
2022 |
|
Date of publication: |
|
27.01.2022 |
