On the model-checking of monadic second-order formulas with edge set quantifications

DOI10.1016/J.DAM.2010.12.017MaRDI QIDQ415286zbMATH OpenOpenAlexFDO

Authors Bruno Courcelle

Publication date 11 May 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2010.12.017

zbMATH Keywords

clique-widthgraph decompositionmodel-checkingmonadic second-order logictree-width

Mathematics Subject Classification ID

Distance in graphs (05C12) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Special tree-width and the verification of monadic second-order graph properties
• Automata for the verification of monadic second-order graph properties
• Computations by fly-automata beyond monadic second-order logic
• On the parameterized intractability of monadic second-order logic
• On the Parameterised Intractability of Monadic Second-Order Logic

Cites work

• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Approximating clique-width and branch-width
• Asteroids in rooted and directed path graphs
• Automata for the verification of monadic second-order graph properties
• Clique-width is NP-complete
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Decidability of S1S and S2S
• Domino Treewidth
• Elements of finite model theory.
• Finding Branch-Decompositions and Rank-Decompositions
• scientific article; zbMATH DE number 3917707 (Why is no real title available?)
• scientific article; zbMATH DE number 1507224 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the clique-width of some perfect graph classes
• On the Relationship Between Clique-Width and Treewidth
• On tree-partition-width
• Parametrized complexity theory.
• The complexity of first-order and monadic second-order logic revisited
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Upper bounds to the clique width of graphs

Cited in

(20)

• Fly-automata for checking \(\mathrm{MSO}_2\) graph properties
• The monadic second-order logic of graphs. XIV: Uniformly sparse graphs and edge set quantifica\-tions.
• Automata for the verification of monadic second-order graph properties
• Grammars and clique-width bounds from split decompositions
• On quasi-planar graphs: clique-width and logical description
• The rank-width of edge-coloured graphs
• Tractability, hardness, and kernelization lower bound for and/or graph solution
• From tree-decompositions to clique-width terms
• Special tree-width and the verification of monadic second-order graph properties
• F-rank-width of (edge-colored) graphs
• Fly-automata for checking monadic second-order properties of graphs of bounded tree-width
• Characterizing width two for variants of treewidth
• The Model Checking Problem for Prefix Classes of Second-Order Logic: A Survey
• Courcelle's theorem -- a game-theoretic approach
• Hypergraphs in Model Checking: Acyclicity and Hypertree-Width versus Clique-Width
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Fully polynomial FPT algorithms for some classes of bounded clique-width graphs
• Computations by fly-automata beyond monadic second-order logic
• Improved (In-)Approximability Bounds for d-Scattered Set
• Enumeration of minimal hitting sets parameterized by treewidth

This page was built for publication: On the model-checking of monadic second-order formulas with edge set quantifications

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