Linear Algebraic Computation of Propositional Horn Abduction

Tuan Nguyen Quoc, Katsumi Inoue, and Chiaki Sakama

Proceedings of IEEE 33rd International Conference on Tools with Artificial Intelligence (ICTAI), pages 240-247.


Linear algebraic characterization of logic programs has been investigated to perform logical inference in large-scale knowledge bases and has gained encouraging results. In this paper, we further extend the linear algebraic characterization in abductive reasoning by exploiting the transpose of the program matrix. Then we propose an efficient exhaustive search strategy, which combines the flexibility and robustness of numerical computation with the compactness and efficiency of set operations, in order to compute solutions of abductive Horn propositional tasks. Experimental results demonstrate that our method is competitive with conflict-driven techniques and has the potential to speed up on parallel computing platforms.

Full Paper (PDF 453K) Slide