Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper explores preprocessing techniques to enhance the efficiency of accessing propositional formulas in conjunctive normal form (CNF), specifically targeting uniform sampling, direct model access, and model enumeration. The authors find that many existing preprocessors fail due to a lack of formula equivalence preservation, while those that maintain model counts can be effectively utilized. Extensive experiments demonstrate that their proposed preprocessing methods significantly improve performance for model access queries in d-DNNF representations across various benchmarks.
Preprocessing techniques that preserve model counts can dramatically boost query efficiency for propositional formulas, challenging the effectiveness of traditional methods.
In this paper, we investigate preprocessing techniques aimed at improving the efficiency of accessing models of propositional formulas represented in conjunctive normal form (CNF). We focus on three fundamental tasks: uniform sampling, direct model access, and model enumeration. Our analysis reveals that most state-of-the-art preprocessors, when they do not preserve formula equivalence, are generally unsuitable for these tasks. In contrast, we demonstrate that preprocessors which preserve model counts can be effectively leveraged, provided relevant preprocessing information is maintained. To validate our approach, we perform extensive experiments on a diverse suite of benchmarks from multiple domains. The experimental results show that our preprocessing methods are both efficient and robust, yielding significant performance improvements for model access queries when CNF formulas are compiled into d-DNNF representations.