Tree-Width for First Order Formulae

DOI10.1007/978-3-642-04027-6_8zbMath1257.03051arXiv1203.3814OpenAlexW1815771810MaRDI QIDQ3644741

Isolde Adler, Mark Weyer

Publication date: 12 November 2009

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

Full work available at URL: https://arxiv.org/abs/1203.3814

Mathematics Subject Classification ID

Logic in computer science (03B70) Classical first-order logic (03B10) Complexity of computation (including implicit computational complexity) (03D15)

Cites Work

• Hypertree decompositions and tractable queries
• Graph searching and a min-max theorem for tree-width
• Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
• Conjunctive query containment revisited
• Conjunctive-query containment and constraint satisfaction
• Directed tree-width examples
• Marshals, monotone marshals, and hypertree-width
• Query evaluation via tree-decompositions
• Constraint solving via fractional edge covers
• Tree-Related Widths of Graphs and Hypergraphs
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Digraph Decompositions and Monotonicity in Digraph Searching
• Computer Science Logic
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Tree-Width for First Order Formulae