Connecting knowledge compilation classes and width parameters
From MaRDI portal
Publication:778533
DOI10.1007/s00224-019-09930-2zbMath1446.68149arXiv1811.02944OpenAlexW2963166380WikidataQ127722524 ScholiaQ127722524MaRDI QIDQ778533
Florent Capelli, Mikaël Monet, Antoine Amarilli, Pierre Senellart
Publication date: 2 July 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1811.02944
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- Graph minors. X: Obstructions to tree-decomposition
- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
- Approximation of boolean functions by combinatorial rectangles
- On the relative succinctness of sentential decision diagrams
- On tree width, bramble size, and expansion
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- Communication Complexity Theory: Thirty-Five Years of Set Disjointness
- No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
- Enumerating All Solutions of a Boolean CSP by Non-decreasing Weight
- Probabilistic Databases
- Combined Tractability of Query Evaluation via Tree Automata and Cycluits
- On Compiling Structured CNFs to OBDDs
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- Provenance Circuits for Trees and Treelike Instances
- A differential approach to inference in Bayesian networks
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- Branching Programs and Binary Decision Diagrams
- Inference and learning in probabilistic logic programs using weighted Boolean formulas
- Exact Model Counting of Query Expressions
- Theory and Applications of Satisfiability Testing
- Decomposable negation normal form
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
