Information loss in knowledge compilation: A comparison of Boolean envelopes
Loading...
Download
Associated Records
Authors
File Licence
Editors
Date
2010-06-01
Source Title
Artificial Intelligence
Journal Title
Journal ISSN
Volume Title
Publisher
ELSEVIER SCIENCE BV
Melbourne Authors
Affiliation
Computer Science and Software Engineering
Document Type
Journal Article
Subject Code
Citation
Schachte, P., Søndergaard, H., Whiting, L. & Henshall, K. (2010). Information loss in knowledge compilation: A comparison of Boolean envelopes. Artificial Intelligence, 174 (9-10), pp.585-596. https://doi.org/10.1016/j.artint.2010.03.003.
Access Status
This item is currently not available from this repository
Access URL
Open Access URL
Open Access at PMC
Linked Resource URL
NHMRC Grant Code
ARC Grant Code
Description
Abstract
Since Selman and Kautz's seminal work on the use of Horn approximation to speed up the querying of knowledge bases, there has been great interest in Boolean approximation for AI applications. There are several Boolean classes with desirable computational properties similar to those of the Horn class. The class of affine Boolean functions, for example, has been proposed as an interesting alternative to Horn for knowledge compilation. To investigate the trade-offs between precision and efficiency in knowledge compilation, we compare, analytically and empirically, four well-known Boolean classes, and their combinations, for ability to preserve information. We note that traditional evaluation which explores unit-clause consequences of random hard 3-CNF formulas does not tell the full story, and we complement that evaluation with experiments based on a variety of assumptions about queries and the underlying knowledge base.
Notes
Terms of Use
Keywords
Artificial Intelligence and Image Processing