Graph-based methods for horn knowledge compression

Peter L. Hammer, Alexander Kogan

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

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 [13] 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.

Original languageEnglish (US)
Title of host publicationProceedings of the Hawaii International Conference on System Sciences
PublisherPubl by IEEE
Pages300-309
Number of pages10
ISBN (Print)0818650702, 9780818650703
DOIs
StatePublished - 1994
EventProceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5) - Wailea, HI, USA
Duration: Jan 4 1994Jan 7 1994

Publication series

NameProceedings of the Hawaii International Conference on System Sciences
Volume3
ISSN (Print)1060-3425

Conference

ConferenceProceedings of the 27th Hawaii International Conference on System Sciences (HICSS-27). Part 4 (of 5)
CityWailea, HI, USA
Period1/4/941/7/94

All Science Journal Classification (ASJC) codes

  • General Computer Science

Fingerprint

Dive into the research topics of 'Graph-based methods for horn knowledge compression'. Together they form a unique fingerprint.

Cite this