Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
| Autor: | Bruno Courcelle |
|---|---|
| Rok vydání: | 2015 |
| Předmět: |
Block graph
Discrete mathematics TheoryofComputation_COMPUTATIONBYABSTRACTDEVICES Applied Mathematics 1-planar graph Combinatorics Treewidth Indifference graph TheoryofComputation_MATHEMATICALLOGICANDFORMALLANGUAGES Pathwidth Chordal graph Clique-width Discrete Mathematics and Combinatorics Graph property Computer Science::Formal Languages and Automata Theory MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Electronic Notes in Discrete Mathematics. 50:3-8 |
| ISSN: | 1571-0653 |
| DOI: | 10.1016/j.endm.2015.07.002 |
| Popis: | Every graph property expressible in monadic second-order (MSO) logic, can be checked in linear time on graphs of bounded tree-width by means of finite automata running on terms denoting tree-decompositions. Implementing these automata is difficult because of their huge sizes. Fly-automata (FA) are deterministic automata that compute the necessary states and transitions when running (instead of looking into tables); they overcome this difficulty. Previously, we constructed FA to check MSO properties of graphs of bounded clique-width. An MSO property with edge quantifications (called an MSO2 property) is an MSO property of the incidence graph and, graphs of tree-width k have incidence graphs of clique-width O ( k ) . Our existing constructions can be used for MSO2 properties of graphs of bounded tree-width. We examine concrete aspects of this adaptation. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect