Research map / Learning theory and algorithms / Combinatorial and search optimization
A Compiler for Weak Decomposable Negation Normal Form
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Integrates weak DNNF (wDNNF) circuits into the knowledge compilation map, proves they are strictly more succinct than DNNF, and presents Bella, a top-down CNF-to-wDNNF compiler built on D4, evaluated on 701 benchmark instances.
Problem
Weak decomposable NNF circuits (which allow restricted variable sharing across AND inputs) had not been analysed in the knowledge compilation map and no compiler existed for them, while DNNF compilation is usually done indirectly via decision-DNNF.
Approach
Extend top-down DNNF compilation with dynamic decomposition in which variables that are pure (only positive or only negative) in a residual CNF may be shared between components, and remove them from the hypergraph used for cut computation, yielding wDNNF circuits directly.
Key results
- Bella compiled every configuration instance, while D4 failed on some, and wDNNF circuits were orders of magnitude smaller on the four most challenging configuration instances (e.g., C202 FS: 4,245,485 vs 154,862,147 for D4).
- Two Bayesian network instances were significantly worse in size and time for wDNNF circuits than for decision-DNNF.
- Theorem shows NNF circuits are strictly more succinct than wDNNF circuits unconditionally (via Tardos' monotone circuit lower bound).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C202 FS | compilation time (s): 1 256.2 -> 66.3 | Helped |
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C202 FS | circuit size: 154 862 147 -> 4 245 485 | Helped |
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C210 FS | compilation time (s): 1 065.3 -> 33.2 | Helped |
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C210 FS | circuit size: 240 087 456 -> 4 300 692 | Helped |
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C210 FW | compilation time (s): 4 048.2 -> 56.7 | Helped |
| Compile configuration instances into wDNNF with Bella instead of decision-DNNF with D4 | CNF configuration instances · C210 FW | circuit size: 715 624 258 -> 6 429 027 | Helped |
Surprising findings
- Two Bayesian network instances are significantly worse for wDNNF circuits, because decisions on pure variables cannot be made since they are excluded from cuts.
- Exactly-one constraints cause almost no variable sharing, so wDNNF gives no advantage on them.
Limitations
- Some Bayesian network instances compile worse because pure variables are excluded from cuts and cannot be chosen as decision variables.
- wDNNF circuits do not satisfy validity, implicant, model counting, sentential entailment, equivalence, forgetting-free conjunction/negation transformations in polynomial time (unless P=NP).
- Evaluation reports only the most important results due to space; compared against D4 and C2D rather than a broader set of compilers.
Experimental setup
Datasets: 701-instance knowledge compilation benchmark set (Lagniez and Marquis 2017)
Benchmarks: 701-instance knowledge compilation benchmark set (BMC, BN, circuit, configuration, handmade, planning, QIF, random)
Metrics: compilation time circuit size number of successful compilations
Baselines: D4 C2D SharpSAT-TD
Builds on: D4 DNNF weak decomposability (Akshay et al. 2018) MiniSat PaToH
Closest papers by meaning
- New Compilation Languages Based on Restricted Weak Decomposability (AAAI 2025 · similarity 0.95)
- An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.87)
- Tensor Decomposition Meets Knowledge Compilation: A Study Comparing Tensor Trains with OBDDs (AAAI 2025 · similarity 0.86)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.85)
- A Compositional Atlas for Algebraic Circuits (NeurIPS 2024 · similarity 0.84)
- Engineering an Exact Pseudo-Boolean Model Counter (AAAI 2024 · similarity 0.82)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.