TL;DR
This paper introduces two new families of canonical representations for knowledge compilation, ROBDD[∧]c and ROBDD[∧T,i]T, which extend existing methods by incorporating conjunctive decomposition. These new representations offer improved succinctness and comparable or better tractability compared to prior approaches, and the authors developed an efficient compiler for them.
What Problem Does This Paper Address?
Knowledge compilation (KC) aims to transform complex knowledge bases into a format that allows for efficient reasoning, particularly for tasks like equivalence testing. Reduced Ordered Binary Decision Diagrams (ROBDDs) are a popular canonical representation in KC due to their constant-time equivalence testing. However, ROBDDs suffer from a significant weakness: they can become exponentially large, leading to a "size explosion" problem. While other representations like d-DNNF and its variants (e.g., ROBDD-L∞, AOBDD) offer better succinctness, they often come with trade-offs in terms of tractability or completeness, and their relationships are not always well understood. This paper addresses the need for canonical representations that balance succinctness and tractability, aiming to mitigate the size explosion of ROBDDs without sacrificing their advantages.
Methods
The core contribution of this paper is the introduction of two new families of canonical representations: ROBDD[∧]c and ROBDD[∧T,i]T. These are built upon the foundation of ROBDDs by incorporating conjunctive decomposition. Specifically:
- Conjunctive Decomposition: The authors generalize existing ideas of conjunctive decomposition (like those in ROBDD-L∞ and AOBDD) into two new types:
- Λi-decomposition: A conjunctive decomposition where at most one conjunct has more than i variables.
- ΛT,i-decomposition: A conjunctive decomposition respecting a given tree structure T, with a bound on the number of variables in conjuncts.
- New Canonical Languages:
- ROBDD[∧]c: This family imposes reducedness, finest Λi-decomposability, and ordered decision respecting a chain C.
- ROBDD[∧T,i]T: This family imposes reducedness, finest ΛT,i-decomposability, and ordered decision respecting a tree T.
- Rapidity: A new criterion called "rapidity" is introduced to measure time efficiency. It considers not just the complexity of an operation on a given representation but also the time it takes to convert to a more succinct representation and then perform the operation. This aims to provide a more practical comparison of time efficiency than tractability alone.
- Compiler Development: The authors developed an efficient compiler for the ROBDD[∧]c representation.
Datasets
Not discussed in the paper. The paper focuses on theoretical properties and experimental evaluation using benchmark domains from the knowledge compilation literature.
Key Insights and Ideas
- Bridging the Gap: The new ROBDD[∧]c and ROBDD[∧T,i]T families effectively bridge the gap between highly succinct but potentially less tractable representations and the more tractable but less succinct ROBDD.
- Hierarchical Succinctness: The paper demonstrates a clear hierarchy of succinctness: ROBDD[∧]c (with increasing i) and ROBDD[∧T,i]T (with increasing i or more complex trees) are generally more succinct than their predecessors.
- Rapidity Matters: The introduction of "rapidity" highlights that even if a representation is less tractable in theory, if it can be efficiently converted to a more succinct form, its practical performance might be superior. This challenges traditional KC maps that solely rely on tractability.
- Completeness vs. Incompleteness: ROBDD[∧]c is shown to be complete, while ROBDD[∧T,i]T can be incomplete if the tree T is not a chain, which is an important consideration for practical use.
Key Results
- Expressivity: ROBDD[∧]c is complete, while ROBDD[∧T,i]T can be incomplete. The expressivity of ROBDD[∧T,i]T is shown to be hierarchical with respect to i.
- Succinctness: ROBDD[∧]c (for i < j) is strictly more succinct than ROBDD[∧;]c. ROBDD[∧T,i]T is at most as succinct as ROBDD[∧]c.
- Tractability: ROBDD[∧]c (for i > 2) maintains the same tractability as ROBDD-L∞. ROBDD[∧T,i]T is at least as tractable as ROBDD, and can be more tractable than ROBDD if the tree depth is limited. Both new families are more tractable than d-DNNF.
- Rapidity: MODS <OP ROBDD[∧]c <OP ROBDD[∧;]c for i < j, and ROBDD[∧T,i]T <OP ROBDD[∧]c. This suggests that for operations where ROBDD[∧]c is more succinct, it is also preferred from a rapidity perspective.
- Experimental Performance: The developed ROBDD[∧]c compiler significantly outperformed ROBDD-L∞ and CSDDy compilers on several benchmark domains and showed comparable performance to the state-of-the-art d-DNNF compiler DSHARP in terms of compiling time and resulting sizes.
Limitations and Future Work
- Incompleteness of ROBDD[∧T,i]T: The ROBDD[∧T,i]T family can be incomplete when the underlying tree structure T is not a chain. This means it might not be able to represent all formulas that ROBDD can.
- Ordering Heuristics: The experimental results for the ROBDD[∧]c compiler showed that ordering heuristics can sometimes have a negative impact on performance for specific domains (e.g., sortnet). Future work could explore more robust ordering strategies.
- Comparison with other d-DNNF variants: While comparisons are made with ROBDD-L∞, AOBDD, and CSDDy, further exploration of relationships with other advanced d-DNNF variants could be beneficial.
- Practical Compiler Enhancements: The paper mentions the development of an efficient compiler. Further optimization and exploration of compiler techniques for these new representations would be valuable.
Summary updated