Approximate Knowledge Compilation: The First Order Case

Abstract

Knowledge compilation procedures make a knowledge base more explicit so as make inference with respect to the compiled knowledge base tractable or at least more efficient. Most work to date in this area has been restricted to the propositional case, despite the importance of first order theories for expressing knowledge concisely. Focusing on (LUB) approximate compilation (Selman and Kautz 1991), our contribution is twofold: ffl We present a new ground algorithm for approximate compilation which can produce exponential savings with respect to the previously known algorithm (Selman and Kautz 1991). ffl We show that both ground algorithms can be lifted to the first order case preserving their correctness for approximate compilation. Introduction Knowledge compilation procedures make a knowledge base (logical theory) \\Sigma more explicit so as make inference with respect to the compiled knowledge base \\Sigma ? tractable, or at least more efficient. The key idea is to invest time and ...