Connecting knowledge compilation classes and width parameters
From MaRDI portal
Publication:778533
DOI10.1007/S00224-019-09930-2zbMATH Open1446.68149arXiv1811.02944OpenAlexW2963166380WikidataQ127722524 ScholiaQ127722524MaRDI QIDQ778533FDOQ778533
Authors: Antoine Amarilli, Florent Capelli, Mikaël Monet, Pierre Senellart 
Publication date: 2 July 2020
Published in: Theory of Computing Systems (Search for Journal in Brave)
Abstract: The field of knowledge compilation establishes the tractability of many tasks by studying how to compile them to Boolean circuit classes obeying some requirements such as structuredness, decomposability, and determinism. However, in other settings such as intensional query evaluation on databases, we obtain Boolean circuits that satisfy some width bounds, e.g., they have bounded treewidth or pathwidth. In this work, we give a systematic picture of many circuit classes considered in knowledge compilation and show how they can be systematically connected to width measures, through upper and lower bounds. Our upper bounds show that bounded-treewidth circuits can be constructively converted to d-SDNNFs, in time linear in the circuit size and singly exponential in the treewidth; and that bounded-pathwidth circuits can similarly be converted to uOBDDs. We show matching lower bounds on the compilation of monotone DNF or CNF formulas to structured targets, assuming a constant bound on the arity (size of clauses) and degree (number of occurrences of each variable): any d-SDNNF (resp., SDNNF) for such a DNF (resp., CNF) must be of exponential size in its treewidth, and the same holds for uOBDDs (resp., n-OBDDs) when considering pathwidth. Unlike most previous work, our bounds apply to any formula of this class, not just a well-chosen family. Hence, we show that pathwidth and treewidth respectively characterize the efficiency of compiling monotone DNFs to uOBDDs and d-SDNNFs with compilation being singly exponential in the corresponding width parameter. We also show that our lower bounds on CNFs extend to unstructured compilation targets, with an exponential lower bound in the treewidth (resp., pathwidth) when compiling monotone CNFs of constant arity and degree to DNNFs (resp., nFBDDs).
Full work available at URL: https://arxiv.org/abs/1811.02944
Recommendations
- Connecting width and structure in knowledge compilation
- Cliquewidth and knowledge compilation
- Parametrization of knowledge structures
- Knowledge compilation using the extension rule
- Knowledge compilation and theory approximation
- scientific article
- scientific article; zbMATH DE number 4061851
- Duality in Knowledge Compilation Techniques
- scientific article; zbMATH DE number 549989
- A framework for method-specific knowledge compilation from databases
Cites Work
- A differential approach to inference in Bayesian networks
- Graph minors. X: Obstructions to tree-decomposition
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Branching Programs and Binary Decision Diagrams
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- On the Tractable Counting of Theory Models and its Application to Truth Maintenance and Belief Revision
- Theory and Applications of Satisfiability Testing
- On the complexity of VLSI implementations and graph representations of Boolean functions with application to integer multiplication
- No Small Nondeterministic Read-Once Branching Programs for CNFs of Bounded Treewidth
- Decomposable negation normal form
- Probabilistic databases
- Inference and learning in probabilistic logic programs using weighted Boolean formulas
- Complexity theoretical results on partitioned (nondeterministic) binary decision diagrams
- Knowledge compilation meets database theory: compiling queries to decision diagrams
- On tree width, bramble size, and expansion
- A \(c^k n\) 5-approximation algorithm for treewidth
- Approximation of boolean functions by combinatorial rectangles
- On the relative succinctness of sentential decision diagrams
- Communication Complexity Theory: Thirty-Five Years of Set Disjointness
- On decomposability and interaction functions
- Enumerating all solutions of a Boolean CSP by non-decreasing weight
- Combined Tractability of Query Evaluation via Tree Automata and Cycluits
- On Compiling Structured CNFs to OBDDs
- Provenance Circuits for Trees and Treelike Instances
- Exact Model Counting of Query Expressions
- Title not available (Why is that?)
Cited In (2)
This page was built for publication: Connecting knowledge compilation classes and width parameters
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q778533)
