Lower bounds on the complexity of MSO₁ model-checking

DOI10.4230/LIPICS.STACS.2012.326zbMATH Open1245.68107MaRDI QIDQ2904773FDOQ2904773

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

Publication date: 23 August 2012

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

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)

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)