Optimal compression of propositional Horn knowledge bases: complexity and approximation
✍ Scribed by Peter L. Hammer; Alexander Kogan
- Publisher
- Elsevier Science
- Year
- 1993
- Tongue
- English
- Weight
- 746 KB
- Volume
- 64
- Category
- Article
- ISSN
- 0004-3702
No coin nor oath required. For personal study only.
✦ Synopsis
Hammer, P.L. and A. Kogan, Optimal compression of propositional Horn knowledge bases: complexity and approximation (Research Note), Artificial Intelligence 64 (1993) 131-145.
Horn formulae play a prominent role in artificial intelligence and logic programming. In this paper we investigate the problem of optimal compression of propositional Horn production rule knowledge bases. The standard approach to this problem, consisting in the removal of redundant rules from a knowledge base, leads to an "irredundant ~ but not necessarily optimal knowledge base. We prove here that the number of rules in any irredundant Horn knowledge base involving n propositional variables is at most n -1 times the minimum possible number of rules. Therefore, the quadratic time transformation of an arbitrary Horn production rule base to an equivalent irredundant and prime one (presented in [9] ) provides a reasonable approximation algorithm.
In order to formalize the optimal compression problem, we define a Boolean function of a knowledge base as being the function whose set of true points is the set of models of