Name
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. |
Year | DOI | Venue |
|---|---|---|
2010 | 10.1016/j.artint.2010.03.003 | Artif. Intell. |
Keywords | Field | DocType |
horn approximation,underlying knowledge base,knowledge base,information loss,boolean envelope,knowledge compilation,well-known boolean class,affine boolean function,boolean approximation,traditional evaluation,horn class,boolean class,boolean function | Maximum satisfiability problem,Boolean function,Discrete mathematics,Boolean circuit,Short-circuit evaluation,Computer science,Theoretical computer science,Standard Boolean model,Boolean expression,Two-element Boolean algebra,Boolean analysis | Journal |
Volume | Issue | ISSN |
174 | 9-10 | 0004-3702 |
Citations | PageRank | References |
1 | 0.35 | 11 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Peter Schachte | 1 | 256 | 22.76 |
| Harald Søndergaard | 2 | 858 | 79.52 |
| Leigh Whiting | 3 | 3 | 1.42 |
| Kevin Henshall | 4 | 3 | 1.42 |