On the Parameterised Intractability of Monadic Second-Order Logic

DOI10.1007/978-3-642-04027-6_26zbMath1257.68070OpenAlexW1843939751MaRDI QIDQ3644759

Stephan Kreutzer

Publication date: 12 November 2009

Published in: Computer Science Logic (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-04027-6_26

Mathematics Subject Classification ID

Specification and verification (program logics, model checking, etc.) (68Q60) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (2)

Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Polynomial treewidth forces a large grid-like-minor
• Elements of finite model theory.
• Graph minors. V. Excluding a planar graph
• Some simplified NP-complete graph problems
• Quickly excluding a planar graph
• Fixed-Parameter Tractability, Definability, and Model-Checking
• Deciding first-order properties of locally tree-decomposable structures

This page was built for publication: On the Parameterised Intractability of Monadic Second-Order Logic