Recognizability equals definability for graphs of bounded treewidth and bounded chordality

DOI10.1016/j.endm.2015.06.076zbMath1346.05249WikidataQ59567455 ScholiaQ59567455MaRDI QIDQ322323

Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle

Publication date: 14 October 2016

Full work available at URL: https://research.tue.nl/nl/publications/48e688fd-945c-4e7a-bdcd-d5f23ff1e7a3

zbMATH Keywords

automata; treewidth; definability; logic; chordality; recognizability

Mathematics Subject Classification ID

05C38: Paths and cycles

05C75: Structural characterization of families of graphs

05C78: Graph labelling (graceful graphs, bandwidth, etc.)

68Q99: Theory of computing