QUASI-ACYCLIC PROPOSITIONAL HORN KNOWLEDGE BASES - OPTIMAL COMPRESSION

Horn knowledge bases are widely used in many applications. This paper is concerned with the optimal compression of propositional Horn produc tion rule bases - one of the most important knowledge bases used in pr actice. The problem of knowledge compression is interpreted as a probl em of Boolean function minimization. It was proved in [16] that the mi nimization of Horn functions, i.e., Boolean functions associated with Horn knowledge bases, is NP-complete. This paper deals with the minimi zation of quasi-acyclic Horn functions, the class of which properly in cludes the two practically significant classes of quadratic and of acy clic functions. A procedure is developed for recognizing in quadratic time the quasi-acyclicity of a function given by a Horn CNF, and a gra ph-based algorithm is proposed for the quadratic time minimization of quasi-acyclic Horn functions.