Decomposing Quantified Conjunctive (or Disjunctive) Formulas

DOI10.1109/LICS.2012.31zbMath1361.68138OpenAlexW1998342956MaRDI QIDQ2986797

Victor Dalmau, Hubie Chen

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 logictreewidthmodel checking

Mathematics Subject Classification ID

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

Related Items (11)

Structural tractability of counting of solutions to conjunctive queries ⋮ Quantified conjunctive queries on partially ordered sets ⋮ Quantified Conjunctive Queries on Partially Ordered Sets ⋮ The complexity of weighted counting for acyclic conjunctive queries ⋮ Quantified Constraints in Twenty Seventeen ⋮ Bounded-width QBF is PSPACE-complete ⋮ On the complexity of existential positive queries ⋮ Unnamed Item ⋮ On the shortest path game ⋮ Characterizing tractability of simple well-designed pattern trees with projection ⋮ Using decomposition-parameters for QBF: mind the prefix!

This page was built for publication: Decomposing Quantified Conjunctive (or Disjunctive) Formulas