On the Parameterized Intractability of Monadic Second-Order Logic

DOI10.2168/LMCS-8(1:27)2012zbMath1238.68067arXiv1203.3167MaRDI QIDQ2881095

Stephan Kreutzer

Publication date: 3 April 2012

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1203.3167

zbMATH Keywords

algorithmic meta-theoremsparameterized complexityfinite model theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60) Model theory of finite structures (03C13)

Related Items (2)

Parameters Tied to Treewidth ⋮ Practical algorithms for MSO model-checking on tree-decomposable graphs

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