On the Parameterised Intractability of Monadic Second-Order Logic

DOI10.1007/978-3-642-04027-6_26MaRDI QIDQ3644759zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• On the parameterized intractability of monadic second-order logic
• Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• The complexity of first-order and monadic second-order logic revisited
• Model checking lower bounds for simple graphs

Cites work

• Algorithmic meta-theorems
• Deciding first-order properties of locally tree-decomposable structures
• Elements of finite model theory.
• Fixed-parameter tractability, definability, and model-checking
• Graph minors. V. Excluding a planar graph
• scientific article; zbMATH DE number 1142315 (Why is no real title available?)
• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Polynomial treewidth forces a large grid-like-minor
• Quickly excluding a planar graph
• Some simplified NP-complete graph problems

Cited in

(17)

• Tree-width and the monadic quantifier hierarchy.
• The complexity of first-order and monadic second-order logic revisited
• Computability by monadic second-order logic
• On the parameterized intractability of monadic second-order logic
• Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking
• Special tree-width and the verification of monadic second-order graph properties
• Parameterized Complexity Results for 1-safe Petri Nets
• SAT in Monadic Gödel Logics: A Borderline between Decidability and Undecidability
• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• On the model-checking of monadic second-order formulas with edge set quantifications
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• Bisimulation Invariant Monadic-Second Order Logic in the Finite
• Model checking lower bounds for simple graphs
• Model checking lower bounds for simple graphs
• Directed Nowhere Dense Classes of Graphs
• MSO undecidability for hereditary classes of unbounded clique width
• MSO undecidability for hereditary classes of unbounded clique-width

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3644759)