Abstract
This paper presents Bella, the first practical knowledge compiler for Weak Decomposable Negation Normal Form (wDNNF). By relaxing the strict variable-sharing constraints of standard Decomposable Negation Normal Form (DNNF), Bella achieves significantly more compact circuit representations for complex Boolean functions. We demonstrate that wDNNF maintains the same level of tractability for key operations, such as consistency checking and model enumeration, while offering superior succinctness, particularly in domains like automotive configuration.
Introduction
Knowledge compilation involves transforming propositional formulas into target languages that support efficient query answering. A central challenge in this field is the trade-off between succinctness (circuit size) and tractability (the efficiency of operations). Decomposable Negation Normal Form (DNNF) has long been a "sweet spot" in this trade-off because it supports many tractable operations. However, its strict decomposability rule—requiring that inputs to an AND gate share no variables—often leads to exponential circuit growth in practice.
Weak Decomposable Negation Normal Form (wDNNF) was proposed to address this by allowing limited variable sharing. Specifically, subcircuits can share variables as long as those variables appear with consistent polarity (only positive or only negative) within those subcircuits. This relaxation allows for more efficient logic decomposition without breaking the tractability of fundamental queries.
The Bella Compiler
Bella is a top-down compiler built upon the architecture of the state-of-the-art D4 compiler. Its primary innovation is Disjoint Component Analysis. While standard compilers like D4 partition clauses into sets with zero shared variables, Bella identifies "weakly" disjoint components. It ignores shared variables that are "pure" (monotonic) within the components, allowing for more aggressive decomposition and smaller resulting circuits.
By treating monotonic variables as "freebies" that can be shared, Bella finds better "cuts" in the logic. This is particularly effective in real-world problems like configuration, where many variables act monotonically.
Evaluation and Results
Bella was evaluated on a benchmark of 701 instances across various domains, including Bounded Model Checking (BMC), Bayesian Networks (BN), and configuration instances.
Succinctness and Performance
The experimental results confirm the theoretical succinctness of wDNNF. Bella consistently produced smaller circuits than the D4 compiler, especially on configuration instances where monotonic variables are prevalent. As shown in the comparison of circuit sizes, Bella's wDNNF representations are often orders of magnitude more compact than standard decision-DNNF circuits.
In the most challenging configuration cases, such as the C202_FS instance, Bella generated circuits that were significantly smaller and compiled faster than competing tools like SharpSAT-TD or c2D. Furthermore, Bella exhibited high reliability, successfully compiling all 35 configuration instances in the dataset, a feat not matched by all other tested compilers.
Conclusion and Future Work
Bella proves that wDNNF is a practical and powerful target language for knowledge compilation. By exploiting monotonicity, it overcomes the size limitations of standard DNNF without sacrificing tractability for consistency checking.
However, some limitations remain. "Exactly-one" constraints are inherently non-monotone and thus do not benefit from weak decomposability. Future research will focus on optimizing heuristics for "pure" variable selection and extending Bella to support deterministic wDNNF, which would enable linear-time model counting.
Summary updated