A Knowledge Compilation Map

Abstract

We propose a perspective on knowledge compilation which calls for analyzing different compilation approaches according to two key dimensions: the succinctness of the target compilation language, and the class of queries and transformations that the language supports in polytime. We then provide a knowledge compilation map, which analyzes a large number of existing target compilation languages according to their succinctness and their polytime transformations and queries. We argue that such analysis is necessary for placing new compilation approaches within the context of existing ones. We also go beyond classical, flat target compilation languages based on CNF and DNF, and consider a richer, nested class based on directed acyclic graphs (such as OBDDs), which we show to include a relatively large number of target compilation languages.

Cited by in corpus (25)

• Inference and learning in probabilistic logic programs using weighted Boolean formulas
• Scaling Exact Inference for Discrete Probabilistic Programs
• Fast counting with tensor networks
• SPPL: Probabilistic Programming with Fast Exact Symbolic Inference
• Three Modern Roles for Logic in AI
• Connecting Knowledge Compilation Classes and Width Parameters
• SAT Encodings for Pseudo-Boolean Constraints Together With At-Most-One Constraints
• Generalising unit-refutation completeness and SLUR via nested input resolution
• MAP Inference for Probabilistic Logic Programming
• Enhancing SMT-based Weighted Model Integration by Structure Awareness
• Semirings for Probabilistic and Neuro-Symbolic Logic Programming
• On the Power of Automata Minimization in Reactive Synthesis
• Local Backbones
• Knowledge Compilation of Logic Programs Using Approximation Fixpoint Theory
• Solving a Special Case of the Intensional vs Extensional Conjecture in Probabilistic Databases
• Reduced Ordered Binary Decision Diagram with Implied Literals: A New knowledge Compilation Approach
• Generating Random Logic Programs Using Constraint Programming
• Probabilistic Answer Set Programming with Discrete and Continuous Random Variables
• Scaling Optimization Over Uncertainty via Compilation
• Inlining External Sources in Answer Set Programs
• The Complexity of Maximal Common Subsequence Enumeration
• Optimizing Probabilities in Probabilistic Logic Programs
• Relation-Stratified Sampling for Shapley Values Estimation in Relational Databases
• Solving Decision Theory Problems with Probabilistic Answer Set Programming
• Nonground Abductive Logic Programming with Probabilistic Integrity Constraints