The hyper system: Knowledge reformation for efficient first-order hypothetical reasoning

We present the HYPER system that implements a new approach to knowledge compilation, where function-free first-order acyclic Horn theories are transformed to propositional logic. The compilation method integrates techniques from deductive databases (relevance reasoning) and theory transformation via unfold/fold transformations, to obtain a compact propositional representation. The transformed theory is more compact than the ground version of the original theory in terms of significantly less and mostly shorter clauses. This form of compilation, called knowledge (base) reformation, is important since the most efficient reasoning methods are defined for propositional theories, while knowledge is most naturally expressed in a first-order language. In particular, we will show that knowledge reformation allows low-order polynomial time inference to find a near-optimal solution in cost-based first-order hypothetical reasoning (or 'abduction') problems. We will also present experimental results that confirm the effectiveness of our compilation method.