Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality
Publication date
2015-11-01
Authors
Bodlaender, Hans
Heggernes, Pinar
Telle, Jan Arne
Editors
Advisors
Supervisors
Document Type
Article
Metadata
Show full item recordCollections
License
taverne
Abstract
We prove that every recognizable family of graphs of bounded treewidth and bounded chordality is definable in counting monadic second-order logic.
Keywords
Automata, Chordality, Definability, Logic, Recognizability, Treewidth, Taverne, Discrete Mathematics and Combinatorics, Applied Mathematics
Citation
Bodlaender, H L, Heggernes, P & Telle, J A 2015, 'Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality', Electronic Notes in Discrete Mathematics, vol. 49, pp. 559-568. https://doi.org/10.1016/j.endm.2015.06.076