Paper Info
Title
Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
Abstract
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.
Year
DOI
Venue
2015
10.1016/j.endm.2015.07.002
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Fixed-parameter tractability,tree-width,incidence graph,clique-width,fly-automaton,monadic second-order logic,edge quantification,model-checking
Block graph,Discrete mathematics,Indifference graph,Combinatorics,Graph property,Chordal graph,Treewidth,Clique-width,Pathwidth,1-planar graph,Mathematics
Journal
Volume
ISSN
Citations 
50
1571-0653
2
PageRank 
References 
Authors
0.36
5
1
Name
Order
Citations
PageRank
Bruno Courcelle13418388.00