DIMACS TR: 93-37

Quasi-Acyclic Propositional Horn Knowledge Bases: Optimal Compression

Authors: Peter L. Hammer and Alexander Kogan


Horn knowledge bases are widely used in many applications. This paper is concerned with the optimal compression of propositional Horn production rule bases - one of the most important knowledge bases used in practice. The problem of knowledge compression is interpreted as a problem of Boolean function minimization. It was proved in [14] that the minimization of Horn functions, i.e. Boolean functions associated to Horn knowledge bases, is NP-complete.

This paper deals with the minimization of quasi-acyclic Horn functions, the class of which properly includes the two practically significant classes of quadratic and of acyclic functions. A procedure is developed for recognizing in quadratic time the quasi-acyclicity of a function given by a Horn CNF, and a graph-based algorithm is proposed for the quadratic time minimization of quasi-acyclic Horn functions.

Paper available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1993/93-37.ps

DIMACS Home Page