Tree-width for first order formulae

DOI10.2168/LMCS-8(1:32)2012MaRDI QIDQ2881100zbMATH OpenOpenAlexFDO

Authors Isolde Adler, Mark Weyer

Publication date 3 April 2012

Published in Logical Methods in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.2168/lmcs-8(1:32)2012

zbMATH Keywords

conjunctive queriescops-and-robbers gameelimination-widthfirst-order logicmodel checkingquantified constraint formulaetreewidth

Mathematics Subject Classification ID

Classical first-order logic (03B10) Subsystems of classical logic (including intuitionistic logic) (03B20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Tree-Width for First Order Formulae
• Model-Checking First-Order Logic: Automata and Locality
• Tree-depth, quantifier elimination, and quantifier rank
• Query evaluation via tree-decompositions
• Twin-width. I: Tractable FO model checking

Cited in

(10)

• Using decomposition-parameters for QBF: mind the prefix!
• How many variables are needed to express an existential positive query?
• Decomposing quantified conjunctive (or disjunctive) formulas
• Tree-Width for First Order Formulae
• Twin-width. I: Tractable FO model checking
• On the complexity of existential positive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
• The theory of concatenation over finite models
• Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity

This page was built for publication: Tree-width for first order formulae

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