Decomposing Quantified Conjunctive (or Disjunctive) Formulas
DOI10.1137/140957378zbMath1355.68174OpenAlexW2549714065MaRDI QIDQ5506695
Publication date: 13 December 2016
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://eprints.bbk.ac.uk/id/eprint/22144/1/paper.pdf
computational complexitymodel checkingquantified formulasquantified conjunctive fragment of first-order logic
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 (1)
Cites Work
- Structural tractability of counting of solutions to conjunctive queries
- Tractable structures for constraint satisfaction with truth tables
- Quantified constraint satisfaction and the polynomially generated powers property
- Hypertree decompositions and tractable queries
- Finite model theory and its applications.
- Oligomorphic clones
- Existentially restricted quantified constraint satisfaction
- A partial k-arboretum of graphs with bounded treewidth
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- Conjunctive-query containment and constraint satisfaction
- Constraint satisfaction with succinctly specified relations
- Hypertree width and related hypergraph invariants
- Parametrized complexity theory.
- The Fine Classification of Conjunctive Queries and Parameterized Logarithmic Space
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Tree-width for first order formulae
- Meditations on Quantified Constraint Satisfaction
- The reducts of equality up to primitive positive interdefinability
- Quantified Constraints and Containment Problems
- The complexity of acyclic conjunctive queries
- Query evaluation via tree-decompositions
- Non-dichotomies in Constraint Satisfaction Complexity
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- One hierarchy spawns another
- Arc consistency and friends
- When is the evaluation of conjunctive queries tractable?
- Block-Sorted Quantified Conjunctive Queries
- Computer Science Logic
- Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- STACS 2005
- A Trichotomy in the Complexity of Counting Answers to Conjunctive Queries
- Qualitative Temporal and Spatial Reasoning Revisited
This page was built for publication: Decomposing Quantified Conjunctive (or Disjunctive) Formulas
