Definability equals recognizability for graphs of bounded treewidth

DOI10.1145/2933575.2934508MaRDI QIDQ4635898zbMATH OpenOpenAlexFDO

Authors Mikołaj Bojańczyk, Michał Pilipczuk

Publication date 23 April 2018

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

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

zbMATH Keywords

treewidthmonadic second-order logicrecognizabilitytree decompositionSimon's factorization forest

Mathematics Subject Classification ID

Automata and formal grammars in connection with logical questions (03D05) Structural characterization of families of graphs (05C75)

Abstract: We prove a conjecture of Courcelle, which states that a graph property is definable in MSO with modular counting predicates on graphs of constant treewidth if, and only if it is recognizable in the following sense: constant-width tree decompositions of graphs satisfying the property can be recognized by tree automata. While the forward implication is a classic fact known as Courcelle's theorem, the converse direction remained open

Recommendations

• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Equivalent definitions of recognizability for sets of graphs of bounded tree-width
• scientific article; zbMATH DE number 1136093
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Definability equals recognizability for k-outerplanar graphs
• Recognizable sets of graphs of bounded tree-width
• Treewidth and logical definability of graph products
• Recognizability equals definability for partial k-paths
• Definability equals recognizability of partial 3-trees and k-connected partial k-trees

Cited in

(23)

• scientific article; zbMATH DE number 7471674 (Why is no real title available?)
• Expressiveness results for an inductive logic of separated relations
• Rank-decreasing transductions
• Treewidth and logical definability of graph products
• Compound logics for modification problems
• Recognizability equals definability for partial k-paths
• Definable decompositions for graphs of bounded linear cliquewidth
• Computing Tree Decompositions
• Definable decompositions for graphs of bounded linear cliquewidth
• Monadic monadic second order logic
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Characterizations of monadic second order definable context-free sets of graphs
• An algorithmic meta theorem for homomorphism indistinguishability
• A complexity approach to tree algebras: the bounded case
• scientific article; zbMATH DE number 2086423 (Why is no real title available?)
• scientific article; zbMATH DE number 7204410 (Why is no real title available?)
• Derivatives on graphs for the positive calculus of relations with transitive closure
• A non-regular language of infinite trees that is recognizable by a sort-wise finite algebra
• Definability equals recognizability for k-outerplanar graphs
• scientific article; zbMATH DE number 7471715 (Why is no real title available?)
• The covering problem
• Definability equals recognizability of partial 3-trees
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees

This page was built for publication: Definability equals recognizability for graphs of bounded treewidth

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