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

DOI10.1016/j.dam.2010.12.017zbMath1236.05143OpenAlexW2088523331MaRDI QIDQ415286

No author found.

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

monadic second-order logicmodel-checkinggraph decompositionclique-widthtree-width

Mathematics Subject Classification ID

Related Items (15)

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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On tree-partition-width
• A recognition algorithm for the intersection graphs of directed paths in directed trees
• The complexity of first-order and monadic second-order logic revisited
• Automata for the verification of monadic second-order graph properties
• 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
• Asteroids in rooted and directed path graphs
• Cosmological lower bound on the circuit complexity of a small problem in logic
• Clique-Width is NP-Complete
• Domino Treewidth
• Decidability of S1S and S2S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• On the Relationship Between Clique-Width and Treewidth
• Finding Branch-Decompositions and Rank-Decompositions

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