Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking

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

zbMATH Keywords

intractabilitytree-widthdigraph widthgraph MSO logic

Mathematics Subject Classification ID

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