Tree-width and the monadic quantifier hierarchy.

DOI10.1016/S0304-3975(02)00449-8zbMath1044.68130OpenAlexW2093898714MaRDI QIDQ1401360

J. P. Mariño, Johann A. Makowsky

Publication date: 17 August 2003

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(02)00449-8

zbMATH Keywords

Monadic second-order logicTree-widthPolynomial hierarchyParametrized complexity

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Related Items (4)

On spectra of sentences of monadic second order logic with counting ⋮ Lower bounds on the complexity of \(\mathsf{MSO}_1\) model-checking ⋮ Are there any good digraph width measures? ⋮ Counting truth assignments of formulas of bounded tree-width or clique-width

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Hyperedge replacement: grammars and languages
• Monadic second-order evaluations on tree-decomposable graphs
• The structure of the models of decidable monadic theories of graphs
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• The polynomial-time hierarchy
• On monadic NP vs monadic co-NP
• Arity and alternation in second-order logic
• Linear time solvable optimization problems on graphs of bounded clique-width
• Upper bounds to the clique width of graphs
• Handle-rewriting hypergraph grammars
• Tree acceptors and some of their applications
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Easy problems for tree-decomposable graphs
• The Complexity of Defining a Relation on a Finite Graph
• Second-order and Inductive Definability on Finite Structures
• Monadic generalized spectra
• Handbook of Graph Grammars and Computing by Graph Transformation
• When is the evaluation of conjunctive queries tractable?
• ON THE CLIQUE–WIDTH OF GRAPH WITH FEW P₄'S
• ON THE CLIQUE-WIDTH OF SOME PERFECT GRAPH CLASSES
• Generalized finite automata theory with an application to a decision problem of second-order logic
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic

This page was built for publication: Tree-width and the monadic quantifier hierarchy.