Definable decompositions for graphs of bounded linear cliquewidth

DOI10.1145/3209108.3209135zbMATH Open1452.03088OpenAlexW2963545495MaRDI QIDQ5145285FDOQ5145285

Authors 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)

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)

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.

Recommendations

• Definable decompositions for graphs of bounded linear cliquewidth
• scientific article; zbMATH DE number 1136093
• Definability equals recognizability for graphs of bounded treewidth
• Linear time solvable optimization problems on graphs of bounded clique-width
• Graphs of linear clique-width at most 3

Cited In (4)

• Context-Free Graph Properties via Definable Decompositions
• Definable decompositions for graphs of bounded linear cliquewidth
• Monadic monadic second order logic
• Grammars and clique-width bounds from split decompositions

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)