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

DOI10.1016/J.ENDM.2015.07.002zbMATH Open1347.03077OpenAlexW2212883086MaRDI QIDQ324700FDOQ324700

Authors: Bruno Courcelle 

Publication date: 17 October 2016

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

Recommendations

• Automata for the verification of monadic second-order graph properties
• Special tree-width and the verification of monadic second-order graph properties
• Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
• Computations by fly-automata beyond monadic second-order logic
• Monadic second order finite satisfiability and unbounded tree-width
• The monadic second-order logic of graphs, II: Infinite graphs of bounded width
• scientific article; zbMATH DE number 1136093
• Verifying monadic second-order properties of graph programs
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

zbMATH Keywords

model checkingclique-widthfixed-parameter tractabilitymonadic second-order logictree-widthedge quantificationfly-automatonincidence graph

Mathematics Subject Classification ID

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

Cites Work

• Linear time solvable optimization problems on graphs of bounded clique-width
• Graph structure and monadic second-order logic. A language-theoretic approach
• Automata for the verification of monadic second-order graph properties
• Title not available (Why is that?)
• The complexity of first-order and monadic second-order logic revisited
• Model-checking by infinite fly-automata
• On the model-checking of monadic second-order formulas with edge set quantifications

Cited In (9)

• Special tree-width and the verification of monadic second-order graph properties
• Automata for the verification of monadic second-order graph properties
• From tree-decompositions to clique-width terms
• Rank-width: algorithmic and structural results
• Computations by fly-automata beyond monadic second-order logic
• Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
• Model-checking by infinite fly-automata
• Fly-automata, their properties and applications
• The behavior of clique-width under graph operations and graph transformations

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q324700)