Algorithms for Propositional KB Approximation

One of the obstacles to the effective compilation of propositional knowledge bases (KBs) using Horn approximations, as introduced by (Selman & Kautz 1991), is the lack of computationally feasible methods for generating Horn bounds. In this paper new algorithms for generating Horn Greatest Lower Bounds (GLB) that can apply to large size KBs, are presented. The approach is extended through a more general target language: the renamable Horn class. The conditions under which a renamable Horn formula is a renamable Horn GLB of a KB are established and algorithms for computing it are derived. These algorithms can be used in the other approaches based on computation of Horn or renamable lower bounds as (Boufkhad et al. 1997). The efficiency of these algorithms and the tightness with respect to the KB in terms of number of models of the bounds, are experimentally evaluated. The renamable Horn GLB proves to be closer to the KB than the Horn GLB.

Authors

• Yacine Boufkhad

Keywords

No keywords are indexed for this paper.