Tree-width and the monadic quantifier hierarchy.

DOI10.1016/S0304-3975(02)00449-8zbMATH Open1044.68130OpenAlexW2093898714MaRDI QIDQ1401360FDOQ1401360

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

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

zbMATH Keywords

Monadic second-order logicTree-widthPolynomial hierarchyParametrized complexity

Mathematics Subject Classification ID

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

Cites Work

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

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)