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

DOI10.1016/J.DAM.2010.12.017zbMATH Open1236.05143OpenAlexW2088523331MaRDI QIDQ415286FDOQ415286

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

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

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)

Cites Work

• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Parametrized complexity theory.
• Approximating clique-width and branch-width
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Clique-Width is NP-Complete
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Title not available (Why is that?)
• On the Relationship Between Clique-Width and Treewidth
• Elements of finite model theory.
• Automata for the verification of monadic second-order graph properties
• Asteroids in rooted and directed path graphs
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• Title not available (Why is that?)
• The complexity of first-order and monadic second-order logic revisited
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Title not available (Why is that?)
• Finding Branch-Decompositions and Rank-Decompositions
• On tree-partition-width
• Domino Treewidth
• Decidability of S1S and S2S

Cited In (18)

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

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)