A Compiler for Weak Decomposable Negation Normal Form

Petr Illner, Petr KuceraAAAI 2024 · DOI

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.

A wDNNF circuit illustrating weak decomposability where subcircuits can share variables with consistent polarity.

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.

Comparison of circuit sizes between Bella (wDNNF) and D4 (decision-DNNF). Points above the diagonal indicate that Bella's wDNNF circuits are more compact than D4's 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

BibTeX
@inproceedings{illner2024compiler,
  author = {Petr Illner and Petr Kucera},
  title = {{A Compiler for Weak Decomposable Negation Normal Form}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2024},
  doi = {10.1609/aaai.v38i9.28926},
}
Figure