Prime Compilation of Non-Clausal Formulae

Alessandro Previti, Alexey Ignatiev, António Morgado, João Marques-SilvaIJCAI 2015

Abstract

Computing prime implicants and implicates is a fundamental task in logic-based AI, essential for model-based diagnosis, formal verification, and knowledge compilation. Traditional methods often struggle with non-clausal formulae due to the "CNF-conversion trap," where conversion leads to exponential size increases or the introduction of auxiliary variables that obscure the original variable space. This paper introduces PRIMe, a SAT-based framework that utilizes a dual-rail encoding to work directly with non-clausal structures. Experimental results demonstrate that PRIMe scales to formulae with thousands of variables, solving over 700 benchmark instances where previous state-of-the-art methods solved only 11.

Introduction

In many real-world applications, such as circuit design and software verification, logic is naturally expressed in non-clausal forms. Compiling these formulae into prime implicants (minimal sets of conditions that make a formula true) or prime implicates (minimal sets of conditions that make it false) is computationally expensive. Existing algorithms typically require input in Conjunctive Normal Form (CNF) or Disjunctive Normal Form (DNF). However, converting non-clausal formulae to these forms often results in an exponential explosion in formula size. Previous non-clausal approaches, largely based on Binary Decision Diagrams (BDDs), generally fail when variable counts exceed a few hundred.

Methodology

The authors propose a reformulation strategy that avoids standard CNF conversion by using a dual-rail encoding. In this scheme, each original variable $v$ is mapped to two variables in a "working formula" $H$, representing whether $v$ is true, false, or absent in a potential prime.

PRIMe implements two primary algorithms:

  1. Basic Algorithm (Algorithm 1): Uses an iterative loop with a SAT solver to find maximal models of $H$. These models are checked against the original formula to extract either a prime implicant or a prime implicate.
  2. Alternative Algorithm (Algorithm 2): Prioritizes finding primes with fewer literals by seeking minimal models, which can reduce the total number of SAT solver calls for certain formula types.

Both algorithms utilize the QuickXplain technique to efficiently minimize satisfying assignments into their prime forms. This dual approach allows for the simultaneous discovery of implicants and implicates, where finding one helps prune the search space for the other.

Experimental Evaluation

The performance of PRIMe was evaluated against the previous state-of-the-art BDD-based tool, ZRes-tison, using three benchmark sets: Quasigroup Classification (QG6), Cryptanalysis (Geffe), and crafted "hard" formulae combining the Pigeonhole Principle and the Ordering Principle.

Table 1: Number of solved instances for ZRes-tison and PRIMe variants across different benchmarks.

As shown in Table 1, PRIMe variants solved significantly more instances than ZRes-tison. Specifically, the "primer-b ($PI_n$)" variant solved 719 instances in total, compared to just 11 for the BDD-based approach.

Figure 1: (a) Scatter plot comparing PRIMe-b with ZRes-tison; (b) Cactus plot showing CPU time vs. number of solved instances.

The scalability of PRIMe is further illustrated in Figure 1. The scatter plot (a) shows that PRIMe-b consistently outperforms ZRes-tison, often by several orders of magnitude. The cactus plot (b) demonstrates that PRIMe can handle hundreds of instances within reasonable time limits, scaling to problems with thousands of variables—a feat previously unattainable for non-clausal prime generation.

Conclusion

By leveraging modern SAT solvers and a direct non-clausal representation, PRIMe overcomes the limitations of BDD-based and CNF-constrained methods. The ability to handle thousands of variables and enumerate hundreds of thousands of primes marks a significant advancement in the field of knowledge compilation. Future work will focus on further optimizing prime extraction and extending these techniques to more complex logic fragments, such as modal logic.

Summary updated

BibTeX
@inproceedings{previti2015prime,
  author = {Alessandro Previti and Alexey Ignatiev and António Morgado and João Marques-Silva},
  title = {{Prime Compilation of Non-Clausal Formulae}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure