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

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item