Definability equals recognizability for graphs of bounded treewidth

DOI10.1145/2933575.2934508zbMATH Open1394.03062arXiv1605.03045OpenAlexW2962996851MaRDI QIDQ4635898FDOQ4635898

Michał Pilipczuk, Mikołaj Bojańczyk

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)

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

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

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

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)

Cited In (12)

• Title not available (Why is that?)
• Title not available (Why is that?)
• Recognizability equals definability for partial k-paths
• Computing Tree Decompositions
• Monadic monadic second order logic
• Recognizability equals definability for graphs of bounded treewidth and bounded chordality
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees
• Title not available (Why is that?)

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)