Selman and Kautz proposed a method, called Horn approximation, for speeding up inference in propositional Knowledge Bases. Their technique is based on the compilation of a propositional formula into a pair of Horn formulae: a Horn Greatest Lower Bound (GLB) and a Horn Least Upper Bound (LUB). In this paper we focus on GLBs and address two questions that have been only marginally addressed so far: (1) what is the semantics of the Horn GLBs? (2) what is the exact complexity of finding them? We obtain semantical as well as computational results. The major semantical result is: The set of minimal models of a propositional formula and the set of minimum models of its Horn GLBs are the same. The major computational result is: Finding a Horn GLB of a propositional formula in CNF is NP-equivalent, (C) 2000 Elsevier Science B.V. All rights reserved.
Semantical and computational aspects of Horn approximations / Cadoli, Marco; Francesco, Scarcello. - In: ARTIFICIAL INTELLIGENCE. - ISSN 0004-3702. - 119:1(2000), pp. 1-17. [10.1016/s0004-3702(00)00010-2]
Semantical and computational aspects of Horn approximations
CADOLI, Marco;
2000
Abstract
Selman and Kautz proposed a method, called Horn approximation, for speeding up inference in propositional Knowledge Bases. Their technique is based on the compilation of a propositional formula into a pair of Horn formulae: a Horn Greatest Lower Bound (GLB) and a Horn Least Upper Bound (LUB). In this paper we focus on GLBs and address two questions that have been only marginally addressed so far: (1) what is the semantics of the Horn GLBs? (2) what is the exact complexity of finding them? We obtain semantical as well as computational results. The major semantical result is: The set of minimal models of a propositional formula and the set of minimum models of its Horn GLBs are the same. The major computational result is: Finding a Horn GLB of a propositional formula in CNF is NP-equivalent, (C) 2000 Elsevier Science B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
