Definable decompositions for graphs of bounded linear cliquewidth

DOI10.1145/3209108.3209135zbMATH Open1452.03088arXiv1803.05937OpenAlexW2963545495MaRDI QIDQ5145285FDOQ5145285

Mikołaj Bojańczyk, Martin Grohe, Michał Pilipczuk

Publication date: 20 January 2021

Published in: Proceedings of the 33rd Annual ACM/IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Abstract: We prove that for every positive integer k, there exists an MSO_1-transduction that given a graph of linear cliquewidth at most k outputs, nondeterministically, some cliquewidth decomposition of the graph of width bounded by a function of k. A direct corollary of this result is the equivalence of the notions of CMSO_1-definability and recognizability on graphs of bounded linear cliquewidth.

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

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Automata and formal grammars in connection with logical questions (03D05) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Higher-order logic (03B16)

Cited In (2)

This page was built for publication: Definable decompositions for graphs of bounded linear cliquewidth

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