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

DOI10.1016/J.ENDM.2015.07.002MaRDI QIDQ324700zbMATHOpenAlexFDO

Authors Bruno Courcelle

Publication date 17 October 2016

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

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)

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

Cites work

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

Cited in

(9)

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

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)