2026-07-24T21:55:22Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:24177 2025-11-12T13:34:07Z ddc:004 open_access

Labelled Well Quasi Ordered Classes of Bounded Linear Clique-Width Lopez, Aliaume well-quasi-ordering linear clique-width MSO transduction automata theory We construct an algorithm that inputs an MSO-interpretation from finite words to graphs, and decides if there exists a k ∈ ℕ such that the class of graphs induced by the interpretation is not well-quasi-ordered by the induced subgraph relation when vertices are freely labelled using {1, …, k}. In case no such k exists, we also prove that the class of graphs is not well-quasi-ordered by the induced subgraph relation when vertices are freely labelled using any well-quasi-ordered set of labels. As a byproduct of our analysis, we prove that for classes of bounded linear clique-width, a weak version of a conjecture by Pouzet holds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aliaume Lopez 2025 Is Part Of LIPIcs, Volume 345, 50th International Symposium on Mathematical Foundations of Computer Science (MFCS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2025.70 urn:nbn:de:0030-drops-241773 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2025.70 eng https://creativecommons.org/licenses/by/4.0/legalcode