Algorithms for Logical Knowledge Bases
This project deals with the exploration of algorithms and methods in
the context of logical knowledge bases (KBs). It is a joint
collaboration with researchers from Kyoto University (Japan). The
goal is to provide efficient algorithms for various computational
problems on knowledge bases which are formulated in a
propositional language. Different issues are researched.
Data and knowledge acquisition. Partially defined Boolean functions
(PDBFs) have been proposed for
representing information about positive and negative logical
correlation of facts. One task is to construct
from such data a KB which is consistent with these data, i.e., a
Boolean function (usually restricted to some class) which interpolates
on these data (called extension). This amounts to specific tasks in the machine
In our project, properties and algorithms for extensions from
different classes of Boolean functions have been explored.
Tractable Inference. Traditionally, pieces of knowledge in KB
are represented through logical formulas, which comprise facts and
rules. A major drawback of this form of representation is that
already in plain languages such as propositional logic, fundamental
reasoning problems (e.g., deciding satisfiability or entailment of a
formula) are computationally intractable. To cope with this, two main
directions have been explored.
Approximation. The contents of a general KB is approximated by some
other KB represented in some tractable language. For example, an
arbitrary propositional KB may be approximated by a Horn propositional
Alternative forms of representation.
The KB is stored using methods different from formulas. For example,
in the model-based reasoning paradigm, a KB is represented by the
characteristic models, which are a subset of its models. Using this approach,
tractable sound and complete reasoning can be asserted for many
classes of knowledge bases where traditional representation is
In our project, we explore algorithms and complexity
issues for approaches in both of the two directions.
- Thomas Eiter, K. Makino, and T. Ibaraki. Double Horn Functions,
Information and Computation , 144:155-190, 1998.
- ---. Two-Face Horn
Extensions, Proceedings Eight
Annual Symposium on Algorithms and Computation (ISAAC '97), pages 112--121,
number 1350 in
LNCS, Singapore, December 17-19, 1997.
- ---. Computing Intersections
of Horn Theories for Reasoning with Models. Proceedings National
Conference on AI (AAAI '98), pages
292-297, Madison, Wisconsin, July 26-30 1998. Full paper
Artificial Intelligence , 110(1-2):57-101, 1999.
- ---. Disjunctions of Horn
Theories and their Cores, Proceedings Ninth Annual Symposium on Algorithms and
Computation (ISAAC '98), pages 49-58, number 1533 in LNCS, Korea, December,
1998. Full paper SIAM Journal on Computing,
- ---. On Disguised Double Horn
Fifteenth Symposium on Theoretical Aspects of Computing (STACS '98), number
1373 in LNCS, pages 50-60, Paris, February 1998.
- ---. On the Difference of
Horn Theories, Proceedings Sixteenth Symposium on Theoretical
Aspects of Computing (STACS '99), pages 448-457, number 1563 in
LNCS, Trier, March,
1999. Full paper Journal of Computer and System
Sciences , 61(3):487-507, 2000.
- ---. Bidual Horn Functions and Extensions, Discrete Applied
Mathematics , special issue on the Satisfiability Problem,
- ---. Decision Lists and Related Boolean Functions,
Theoretical Computer Science, 270(1-2):493-524, 2002.
- ---. Recognition and Dualization of Disguised Bidual Horn
Functions, Information Processing Letters , to appear.