Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
From MaRDI portal
Publication:395003
DOI10.1016/j.jcss.2013.07.005zbMath1311.68087arXiv1109.5804OpenAlexW1542572884MaRDI QIDQ395003
Peter Rossmanith, Alexander Langer, Jan Obdržálek, Somnath Sikdar, Robert Ganian, Petr Hliněný
Publication date: 28 January 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1109.5804
Specification and verification (program logics, model checking, etc.) (68Q60) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
First-order Logic with Connectivity Operators, Are there any good digraph width measures?, Parameters Tied to Treewidth, Approximation algorithms for digraph width parameters, Boolean functional synthesis: hardness and practical algorithms, An Experimental Study of the Treewidth of Real-World Graph Data
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Polynomial treewidth forces a large grid-like-minor
- The polynomial-time hierarchy
- Tree-width and the monadic quantifier hierarchy.
- Which problems have strongly exponential complexity?
- Uniformly hard languages.
- Linear time solvable optimization problems on graphs of bounded clique-width
- Robust simulations and significant separations
- Strong edge-coloring of graphs with maximum degree 4 using 22 colors
- Parametrized complexity theory.
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Are There Any Good Digraph Width Measures?
- On the Parameterised Intractability of Monadic Second-Order Logic
- Directed Nowhere Dense Classes of Graphs