Tree-width and the monadic quantifier hierarchy.
From MaRDI portal
Publication:1401360
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
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 P4'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
