MSO undecidability for hereditary classes of unbounded clique width

DOI10.4230/LIPICS.CSL.2022.17MaRDI QIDQ6124948zbMATH OpenFDO

Authors Anuj Dawar, Abhisekh Sankaran

Publication date 10 April 2024

Full work available at URL https://arxiv.org/abs/2011.02894

zbMATH Keywords

antichainclique widthgridMSO interpretationSeese's conjecture

Mathematics Subject Classification ID

Logic in computer science (03B70)

Recommendations

• MSO undecidability for hereditary classes of unbounded clique-width
• The monadic second-order logic of graphs. XV: On a conjecture by D. Seese
• Vertex-minors, monadic second-order logic, and a conjecture by Seese
• On the Parameterised Intractability of Monadic Second-Order Logic
• The structure of the models of decidable monadic theories of graphs

Cited in

(2)

• \(t\)-sails and sparse hereditary classes of unbounded tree-width
• MSO undecidability for hereditary classes of unbounded clique-width

This page was built for publication: MSO undecidability for hereditary classes of unbounded clique width

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6124948)