Lower bounds on the complexity of MSO₁ model-checking

DOI10.4230/LIPICS.STACS.2012.326MaRDI QIDQ2904773zbMATH OpenFDO

Authors Robert Ganian, Petr Hliněný, Alexander Langer, Jan Obdržálek, Somnath Sikdar, Peter Rossmanith

Publication date 23 August 2012

zbMATH Keywords

treewidthlower boundsexponential time hypothesismonadic second-order logicparameterized complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Specification and verification (program logics, model checking, etc.) (68Q60) Decidability of theories and sets of sentences (03B25)

Recommendations

• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• On the Parameterised Intractability of Monadic Second-Order Logic
• On the parameterized intractability of monadic second-order logic
• Model checking lower bounds for simple graphs
• Model checking lower bounds for simple graphs

Cited in

(8)

• Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking
• Practical algorithms for MSO model-checking on tree-decomposable graphs
• On the parameterized intractability of monadic second-order logic
• Model checking lower bounds for simple graphs
• Digraph width measures in parameterized algorithmics
• On the Parameterised Intractability of Monadic Second-Order Logic
• Model checking lower bounds for simple graphs
• The complexity of first-order and monadic second-order logic revisited

This page was built for publication: Lower bounds on the complexity of \(\mathrm{MSO}_1\) model-checking

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