Definable decompositions for graphs of bounded linear cliquewidth

DOI10.1145/3209108.3209135MaRDI QIDQ5145285zbMATH OpenOpenAlexFDO

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

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

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)

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

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)