Compact Propositional Encodings of First-Order Theories
Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence. Pages 1579-1579.
© 2005 International Joint Conferences on Artificial Intelligence
Abstract
- [Amir and McIlraith, 2004] E. Amir and S. McIlraith. Partition- based logical reasoning for first-order and propositional theories. Artificial Intelligence, 2004. Accepted for publication.
- [Amir, 2001] E. Amir. Efficient approximation for triangulation of minimum treewidth. In UAI'01, pages 7-15.
- Morgan Kaufmann, 2001.
- [Börger et al., 1996] E. Börger, E. Grädel, and Y. Gurevich. The Classical Decision Problem. Springer-Verlag, 1996.
- [Gilmore, 1960] P.C. Gilmore. A proof method for quantification theory: It's justification and realization. IBM Journal of Research and Development, 4(1):28-35, January 1960.
- [Kautz and Selman, 1996] H. Kautz and B. Selman. Pushing the envelope: Planning, propositional logic, and stochastic search. In AAAI'96, 1996.
- [Krogel et al., 2003] M. Krogel, N. Lavrac, and S. Wrobel. Com- parative evaluation of approaches to propositionalization. In ILP, pages 197-214, 2003.
- [Kropf, 1999] T. Kropf, editor. Introduction to Formal Hardware Verification. Springer, 1999.
- [Moskewicz et al., 2001] M. W. Moskewicz, C. F. Madigan, Y. Zhao, L. Zhang, and S. Malik. Chaff: Engineering an effi- cient SAT solver. In Proceedings of the 38th Design Automation Conference (DAC'01), 2001.
References were extracted automatically from the PDF and may contain errors.
Full text extracted automatically from the PDF; figures, tables and equations may differ. The PDF is the version of record.
1 Introduction
A propositionalization of a theory in First-Order Logic (FOL) is a set of propositional sentences that is satisfiable iff the original theory is satisfiable. We cannot translate arbitrary FOL theories to propositional logic because FOL is only semi-decidable. However, when possible, it is often advantageous to do so because we can use optimized, efficient SAT solvers (e.g. [Moskewicz et al., 2001]) to solve the resulting SAT problem. Propositionalization is used frequently in Planning [Kautz and Selman, 1996], Relational Data Mining [Krogel et al., 2003], and Formal Verification [Kropf, 1999].
Current propositional encodings (naive prop.), based on [Gilmore, 1960], result in prohibitively large propositional encodings even for moderate applications and assume a known finite domain for the theory. However despite their drawbacks, they are the most efficient solutions known so far. Examples of naive prop. are given in Table 1.
We briefly describe a novel, systematic approach to translating two important subsets of FOL into propositional logic. Our approach leverages structure in the FOL formulation to provide significantly more compact propositional encodings without requiring a finite fixed domain.
Specifically, we present algorithms for translating two important decidable subsets of FOL: (1) function-free monadic, and (2) the Bernays-Sch¨ oenfinkel-Ramsey class (see [B¨ orger et al., 1996]) in which all existential quantifiers must occur before all universal ones (all arity is allowed for predicates, with equality, but no functions). These subsets cover important problems in AI and computer science, such as expressive planning, data mining, constraint satisfaction, propositional modal logic, and quantified boolean formulae (QBF).
Our algorithms generate propositional encodings of these subsets of FOL as follows. They start by grouping axiom sets into a tree of partitions following the approach of [Amir and McIlraith, 2004]. Then, they translate each partition separately using only a restricted set of constants that depend on shown to be equisatisfiable with A. The proof relies on the completeness of the message passing procedure. Briefly, it can be shown that if the intersection graph of the partitioning is a tree, for every formula α s.t. A ⊢ α, there is a proof s.t. each step uses either axioms that are completely within the same partition Ai or messages transmitted to Ai from other partitions. The proof of this relies on the following theorem:
| FOL Theory | Naive Prop. |
|---|---|
| ¬(P (a)∧Q(b)) | ¬(Pa∧Qb) |
| ∀xP(x) ⇒ ∀y¬Q(y) | (Pa∧Pb∧Pc ⇒ (¬Qa∧¬Qb∧¬Qc)) |
| ∃z(R(z, c)∧¬Q(a)) | (R(a, c)∧¬Q(a))∨(R(c, c)∧¬Q(a)) |

Theorem 1 (Craig's Interpolation Theorem). If α and β are first order formula s.t. α ⊢ β, then there is a formula γ ∈ L(L(α) ∩ L(β)) such that α ⊢ γ and γ ⊢ β.
3 Partitioned Prop. for the Ramsey Class
It is known that the naive partitioning is correct for the Ramsey class without any additional semantic assumptions [B¨ orger et al., 1996]. The number of propositional symbols used is |P||C|k where k is the maximum arity of any predicate. This can be significantly reduced by partitioning. But it is not enough to propositionalize each partition individually. For example, consider the case where P(c) and ∀x[P(x) ⇒ Q(a)] are in different partitions. Because we propositionalize these separately, P(c) ⇒ Q(a) will not be in the propositional theory and thus Q(a) cannot be deduced.
However, it can be shown that there exists an ordering ≺ of the vertices in the intersection graph of the partitioning such that a correct propositionalization results if we propositionalize the predicates of each partition Ai w.r.t. every constant that occurs in some partition Aj, Aj ≺ Ai. For example, in a prop. of the theory in figure 1 a), P3h3 will be in the language, but P1h2 will not. There are n such orderings, one for each choice of a partition as the root of the tree. In the case of a binary tree with n vertices (figure 2) each prop. will have logn n |P||C|k variables. Thus the problem of satisfiability of A reduces to n independent SAT instance of size log n n |P||C|k . The running time will be O(n · 2 logn n |P||C|k ) compared to the naive prop. which takes O(2|P||C|k ).
4 Experimental Results
In figure 3 we present the results of some experiments with our algorithms on two different problems. The first is a firstorder encoding of the pigeonhole problem that belongs to the Ramsey class. The upper two graphs compare our Ramsey prop. with the naive prop. for this problem, on the basis of the number of variables created and the running time for the SAT solver. Our algorithm does substantially better, enabling the solution of problems that are outside the scope of the naive encoding. The size of the encoding for the partitioned Ramsey prop. grows as O(p logp) versus O(p2) for the naive prop, where p is the number of pigeons. The running time for our SAT solver shows orders of magnitude speedup.
The bottom two graphs present a similar comparison for a partitioned pigeonhole problem (i.e. where each pigeon can be assigned only to a fixed subset of the holes) which is in both the Ramsey and Monadic classes. We compare both the Monadic and Ramsey partitioned prop. with naive prop. For the naive prop., the size of the encoding grows as O(p2 ) versus O(p) for the partitioned monadic prop.
The experiments were done on a 3.2 GHz Linux machine with Zchaff [Moskewicz et al., 2001] as the SAT solver.

@inproceedings{ijcai2005p329,
title = {Compact Propositional Encodings of First-Order Theories},
author = {Ramachandran, Deepak and Amir, Eyal},
booktitle = {Proceedings of the Nineteenth International Joint Conference on
Artificial Intelligence, {IJCAI-05}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Leslie Pack Kaelbling and Alessandro Saffiotti},
pages = {1579--1579},
year = {2005},
url = {https://ijcai.org/proceedings/2005/329},
}
TY - CPAPER TI - Compact Propositional Encodings of First-Order Theories AU - Ramachandran, Deepak AU - Amir, Eyal T2 - Proceedings of the Nineteenth International Joint Conference on Artificial Intelligence, IJCAI-05 PB - International Joint Conferences on Artificial Intelligence PY - 2005 SP - 1579 EP - 1579 UR - https://ijcai.org/proceedings/2005/329 ER -Copied
Machine-readable versions of this paper, for tools and AI agents: