Tree-width and the monadic quantifier hierarchy.
type: Item
instance of: scholarly article
title: Tree-width and the monadic quantifier hierarchy.
zbMATH Open document ID: 1044.68130
DOI: 10.1016/S0304-3975(02)00449-8
author: J. P. Mariño
author: Johann A. Makowsky
published in: Theoretical Computer Science
publication date: 2003-08-17T00:00:00Z
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1965369
zbMATH Keywords: Parametrized complexity
zbMATH Keywords: Polynomial hierarchy
zbMATH Keywords: Monadic second-order logic
zbMATH Keywords: Tree-width
MaRDI profile type: Publication
cites work: Easy problems for tree-decomposable graphs
cites work: The Complexity of Defining a Relation on a Finite Graph
cites work: Q3795218
cites work: Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
cites work: Q4508369
cites work: The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
cites work: Handbook of Graph Grammars and Computing by Graph Transformation
cites work: Q4852905
cites work: Handle-rewriting hypergraph grammars
cites work: Linear time solvable optimization problems on graphs of bounded clique-width
cites work: On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
cites work: Monadic second-order evaluations on tree-decomposable graphs
cites work: Upper bounds to the clique width of graphs
cites work: Second-order and Inductive Definability on Finite Structures
cites work: Tree acceptors and some of their applications
cites work: Monadic generalized spectra
cites work: On monadic NP vs monadic co-NP
cites work: Q4198056
cites work: Q4128417
cites work: ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
cites work: When is the evaluation of conjunctive queries tractable?
cites work: Q2766682
cites work: Hyperedge replacement: grammars and languages
cites work: Arity and alternation in second-order logic
cites work: ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P4'S
cites work: Q4218948
cites work: The structure of the models of decidable monadic theories of graphs
cites work: Q3048241
cites work: Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
cites work: The polynomial-time hierarchy
cites work: Generalized finite automata theory with an application to a decision problem of second-order logic
full work available at URL: s0304-3975(02)00449-8
OpenAlex ID: W2093898714
description: scientific article; zbMATH DE number 1965369