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 learning area.

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 KB.
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 intractable.

In our project, we explore algorithms and complexity issues for approaches in both of the two directions.

Selected Publications

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, 31(1):269-288, 2001.
---. On Disguised Double Horn Functions, Proceedings 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, 96/97:55-88, 1999.
---. 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.