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 decompositionmonadic second-order logictree-widthmodel-checking

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Distance in graphs (05C12) 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

• 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?)
• 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
• Linear time solvable optimization problems on graphs of bounded clique-width
• On the Relationship Between Clique-Width and Treewidth
• On the clique-width of some perfect graph classes
• 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

(19)

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

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)