Decomposing quantified conjunctive (or disjunctive) formulas

DOI10.1109/LICS.2012.31MaRDI QIDQ2986797zbMATH OpenOpenAlexFDO

Authors Hubie Chen, Víctor Dalmau

Publication date 16 May 2017

Published in 2012 27th Annual IEEE Symposium on Logic in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1109/lics.2012.31

zbMATH Keywords

computational complexityfirst-order logicmodel checkingtreewidth

Mathematics Subject Classification ID

Subsystems of classical logic (including intuitionistic logic) (03B20) Descriptive complexity and finite models (68Q19) Analysis of algorithms and problem complexity (68Q25) Specification and verification (program logics, model checking, etc.) (68Q60)

Recommendations

• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• On the complexity of the model checking problem
• Tree-Width for First Order Formulae
• Tree-width for first order formulae
• Generalized model-checking over locally tree-decomposable classes

Cited in

(15)

• Characterizing tractability of simple well-designed pattern trees with projection
• Using decomposition-parameters for QBF: mind the prefix!
• Bounded-width QBF is PSPACE-complete
• Using binary patterns for counting falsifying assignments of conjunctive forms
• Quantified conjunctive queries on partially ordered sets
• Structural tractability of counting of solutions to conjunctive queries
• Quantified conjunctive queries on partially ordered sets
• On the complexity of the model checking problem
• The complexity of weighted counting for acyclic conjunctive queries
• Quantified Constraints in Twenty Seventeen
• scientific article; zbMATH DE number 7561480 (Why is no real title available?)
• On the complexity of existential positive queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• Generalized model-checking over locally tree-decomposable classes
• On the shortest path game

This page was built for publication: Decomposing quantified conjunctive (or disjunctive) formulas

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