Tree-width and the monadic quantifier hierarchy.

DOI10.1016/S0304-3975(02)00449-8MaRDI QIDQ1401360zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the Parameterised Intractability of Monadic Second-Order Logic
• The structure of the models of decidable monadic theories of graphs
• On the parameterized intractability of monadic second-order logic
• The monadic second-order logic of graphs III : tree-decompositions, minors and complexity issues
• Easy problems for tree-decomposable graphs

Cites work

• scientific article; zbMATH DE number 1696534 (Why is no real title available?)
• scientific article; zbMATH DE number 3642704 (Why is no real title available?)
• scientific article; zbMATH DE number 4060712 (Why is no real title available?)
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1223636 (Why is no real title available?)
• scientific article; zbMATH DE number 1512682 (Why is no real title available?)
• scientific article; zbMATH DE number 809155 (Why is no real title available?)
• Arity and alternation in second-order logic
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Context-free grammars as a tool for describing polynomial-time subclasses of hard problems
• Easy problems for tree-decomposable graphs
• Generalized finite automata theory with an application to a decision problem of second-order logic
• Handbook of Graph Grammars and Computing by Graph Transformation
• Handle-rewriting hypergraph grammars
• Hyperedge replacement: grammars and languages
• Linear time solvable optimization problems on graphs of bounded clique-width
• Monadic generalized spectra
• Monadic second-order evaluations on tree-decomposable graphs
• On monadic NP vs monadic co-NP
• On the clique-width of graph with few \(P_{4}\)'s
• On the clique-width of some perfect graph classes
• On the fixed parameter complexity of graph enumeration problems definable in monadic second-order logic
• Second-order and Inductive Definability on Finite Structures
• The Complexity of Defining a Relation on a Finite Graph
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The polynomial-time hierarchy
• The structure of the models of decidable monadic theories of graphs
• Tree acceptors and some of their applications
• Upper bounds to the clique width of graphs
• When is the evaluation of conjunctive queries tractable?

Cited in

(5)

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

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1401360)