Definability equals recognizability for graphs of bounded treewidth

DOI10.1145/2933575.2934508zbMath1394.03062arXiv1605.03045OpenAlexW2962996851MaRDI QIDQ4635898

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)

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

zbMATH Keywords

monadic second-order logictreewidthtree decompositionrecognizabilitySimon's factorization forest

Mathematics Subject Classification ID

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

Related Items (8)

Computing Tree Decompositions ⋮ Unnamed Item ⋮ Definability equals recognizability for \(k\)-outerplanar graphs and \(l\)-chordal partial \(k\)-trees ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Unnamed Item

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