The complexity of weighted counting for acyclic conjunctive queries
From MaRDI portal
Publication:395018
DOI10.1016/J.JCSS.2013.08.001zbMath1311.68052arXiv1110.4201OpenAlexW2036350338MaRDI QIDQ395018
Publication date: 28 January 2014
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1110.4201
Related Items (4)
Structural tractability of counting of solutions to conjunctive queries ⋮ The arithmetic complexity of tensor contraction ⋮ Answer Counting under Guarded TGDs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Tractable counting of the answers to conjunctive queries
- The complexity of weighted and unweighted \(\#\)CSP
- On the expressive power of CNF formulas of bounded tree- and clique-width
- Arithmetization: A new method in structural complexity theory
- Hypertree decompositions and tractable queries
- Elements of finite model theory.
- The complexity of counting homomorphisms seen from the other side
- Exact algorithms and applications for tree-like Weighted Set Cover
- A unified theory of structural tractability for constraint satisfaction problems
- Counting truth assignments of formulas of bounded tree-width or clique-width
- Characterizing Valiant's algebraic complexity classes
- Parametrized complexity theory.
- Subtractive reductions and complete problems for counting complexity classes
- On the complexity of #CSP
- Tractable hypergraph properties for constraint satisfaction and conjunctive queries
- Decomposing Quantified Conjunctive (or Disjunctive) Formulas
- Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems
- Degrees of acyclicity for hypergraphs and relational database schemes
- The complexity of acyclic conjunctive queries
- Query evaluation via tree-decompositions
- The Complexity of the Counting Constraint Satisfaction Problem
- The complexity of homomorphism and constraint satisfaction problems seen from the other side
- On Acyclic Conjunctive Queries and Constant Delay Enumeration
- The Complexity of Weighted Boolean #CSP
- Universality considerations in VLSI circuits
- The Parameterized Complexity of Counting Problems
- When is the evaluation of conjunctive queries tractable?
- Complexity of counting CSP with complex weights
- Theory and Applications of Satisfiability Testing
This page was built for publication: The complexity of weighted counting for acyclic conjunctive queries
