Decomposing Quantified Conjunctive (or Disjunctive) Formulas
From MaRDI portal
Recommendations
- Decomposing quantified conjunctive (or disjunctive) formulas
- Decomposing generalized quantifiers
- Representing conjunctive deductions by disjunctive deductions
- On tractability of disjoint AND-decomposition of Boolean formulas
- First-Order Formulas in Conjunctive Quantificational Form
- scientific article; zbMATH DE number 3880597
- On decomposability in logical calculi
- Quantitative disjunctive logic programming: Semantics and computation
- Reconstruction of Boolean formulas in conjunctive normal form
- A simplification for some disjunctive formulations
Cites work
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- A dichotomy theorem for constraint satisfaction problems on a 3-element set
- A partial k-arboretum of graphs with bounded treewidth
- A trichotomy in the complexity of counting answers to conjunctive queries
- Arc consistency and friends
- Beyond Hypertree Width: Decomposition Methods Without Decompositions
- Block-Sorted Quantified Conjunctive Queries
- Computer Science Logic
- Conjunctive-query containment and constraint satisfaction
- Constraint satisfaction with succinctly specified relations
- Existentially restricted quantified constraint satisfaction
- Finite model theory and its applications.
- Hypertree decompositions and tractable queries
- Hypertree width and related hypergraph invariants
- Meditations on quantified constraint satisfaction
- Non-dichotomies in Constraint Satisfaction Complexity
- Oligomorphic clones
- One hierarchy spawns another: graph deconstructions and the complexity classification of conjunctive queries
- Parametrized complexity theory.
- Qualitative temporal and spatial reasoning revisited
- Quantified Constraints and Containment Problems
- Quantified constraint satisfaction and the polynomially generated powers property
- Query evaluation via tree-decompositions
- Robbers, marshals, and guards: Game theoretic and logical characterizations of hypertree width.
- STACS 2005
- Structural tractability of counting of solutions to conjunctive queries
- The Complexity of Quantified Constraint Satisfaction: Collapsibility, Sink Algebras, and the Three-Element Case
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The complexity of acyclic conjunctive queries
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- The fine classification of conjunctive queries and parameterized logarithmic space
- The reducts of equality up to primitive positive interdefinability
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Tractable structures for constraint satisfaction with truth tables
- Tree-width for first order formulae
- Treewidth: A Useful Marker of Empirical Hardness in Quantified Boolean Logic Encodings
- When is the evaluation of conjunctive queries tractable?
Cited in
(7)- On the complexity of the model checking problem
- Decomposing quantified conjunctive (or disjunctive) formulas
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- Using binary patterns for counting falsifying assignments of conjunctive forms
- Small resolution proofs for QBF using dependency treewidth
- Optimally rewriting formulas and database queries: a confluence of term rewriting, structural decomposition, and complexity
- Using decomposition-parameters for QBF: mind the prefix!
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 Q5506695)
