Fly-automata for checking monadic second-order properties of graphs of bounded tree-width

DOI10.1016/J.ENDM.2015.07.002zbMath1347.03077OpenAlexW2212883086MaRDI QIDQ324700

No author found.

Publication date: 17 October 2016

Full work available at URL: https://doi.org/10.1016/j.endm.2015.07.002

zbMATH Keywords

monadic second-order logicmodel checkingfixed-parameter tractabilityclique-widthtree-widthincidence graphedge quantificationfly-automaton

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Automata and formal grammars in connection with logical questions (03D05) Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Related Items (4)

Rank-width: algorithmic and structural results ⋮ From tree-decompositions to clique-width terms ⋮ The behavior of clique-width under graph operations and graph transformations ⋮ Computations by fly-automata beyond monadic second-order logic

Cites Work

• Unnamed Item
• Unnamed Item
• On the model-checking of monadic second-order formulas with edge set quantifications
• The complexity of first-order and monadic second-order logic revisited
• Automata for the verification of monadic second-order graph properties
• Linear time solvable optimization problems on graphs of bounded clique-width
• Model-Checking by Infinite Fly-Automata

This page was built for publication: Fly-automata for checking monadic second-order properties of graphs of bounded tree-width