"Paris" . . . . . . "Sikdar, Somnath" . . . "Lower Bounds on the Complexity of MSO_1 Model-Checking" . . . "Rossmanith, Peter" . "http://stacs2012.lip6.fr/" . . "10.4230/LIPIcs.STACS.2012.326" . "Lower Bounds on the Complexity of MSO_1 Model-Checking"@en . "Langer, Alexander" . "1868-8969" . "Lower Bounds on the Complexity of MSO_1 Model-Checking" . . "29th International Symposium on Theoretical Aspects of Computer Science STACS2012" . . "6"^^ . "RIV/00216224:14330/12:00057595" . "Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, LIPICS" . "2012-01-01+01:00"^^ . . . "Lower Bounds on the Complexity of MSO_1 Model-Checking"@en . "[800792753F08]" . . "Monadic Second-Order Logic; Treewidth; Lower Bounds; Exponential Time Hypothesis; Parameterized Complexity"@en . "14330" . "3"^^ . "12"^^ . "Hlin\u011Bn\u00FD, Petr" . "Dagstuhl, Germany" . . "147519" . "Obdr\u017E\u00E1lek, Jan" . . . "P(GAP202/11/0196), S" . "One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result." . "9783939897354" . . . . . "One of the most important algorithmic meta-theorems is a famous result by Courcelle, which states that any graph problem definable in monadic second-order logic with edge-set quantifications (MSO2) is decidable in linear time on any class of graphs of bounded tree-width. In the parlance of parameterized complexity, this means that MSO2 model-checking is fixed-parameter tractable with respect to the tree-width as parameter. Recently, Kreutzer and Tazari proved a corresponding complexity lower-bound---that MSO2 model-checking is not even in XP wrt the formula size as parameter for graph classes that are subgraph-closed and whose tree-width is poly-logarithmically unbounded. Of course, this is not an unconditional result but holds modulo a certain complexity-theoretic assumption, namely, the Exponential Time Hypothesis (ETH). In this paper we present a closely related result."@en . "RIV/00216224:14330/12:00057595!RIV13-GA0-14330___" . "Ganian, Robert" .