Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality

Hans L. Bodlaender, Pinar Heggernes, Jan Arne Telle

    Research output: Contribution to journalArticleAcademicpeer-review

    Abstract

    We prove that every recognizable family of graphs of bounded treewidth and bounded chordality is definable in counting monadic second-order logic.

    Original languageEnglish
    Pages (from-to)559-568
    Number of pages10
    JournalElectronic Notes in Discrete Mathematics
    Volume49
    DOIs
    Publication statusPublished - 1 Nov 2015

    Keywords

    • Automata
    • Chordality
    • Definability
    • Logic
    • Recognizability
    • Treewidth

    Fingerprint

    Dive into the research topics of 'Recognizability Equals Definability for Graphs of Bounded Treewidth and Bounded Chordality'. Together they form a unique fingerprint.

    Cite this