Abstract
We present and evaluate a new compiler, called d4, targeting the Decision-DNNF language.
As the state-of-the-art compilers C2D and Dsharp targeting the same language,
d4 is a top-down tree-search algorithm exploring the space of propositional
interpretations. d4 is based on the same ingredients as those considered in C2D and Dsharp
(mainly, disjoint component analysis, conflict analysis and non-chronological backtracking, component caching).
d4 takes advantage of a dynamic decomposition approach based on hypergraph partitioning, used sparingly.
Some simplification rules are also used to minimize the time spent in the partitioning steps and to promote the
quality of the decompositions. Experiments show that the compilation times and the sizes of the
Decision-DNNF representations computed by d4 are in many cases significantly lower than the
ones obtained by C2D and Dsharp.
Keywords
- Constraints and Satisfiability: Solvers and Tools
- Knowledge Representation, Reasoning, and Logic: Tractable languages and knowledge compilation
