Linear Algebraic Partial Evaluation of Logic Programs

Tuan Nguyen Quoc, Katsumi Inoue, and Chiaki Sakama

Proceedings of IEEE 36th International Conference on Tools with Artificial Intelligence (ICTAI), pages 355-362.

Abstract

In logic programming, partial evaluation (PE) performs unfolding rules in advance to reduce the cost of inferencing. Recently, PE of logic programs has been implemented in vector spaces by computing the powers of matrix representations. It has been reported that linear algebraic PE substantially enhances the practical performance of linear algebraic methods for logic programming. However, most recent research has focused exclusively on And-rules, assuming that their dependency graph is acyclic. In this paper, we introduce cycle-resolving techniques to ensure that linear algebraic PE works effectively even with cycles in the program. Additionally, we demonstrate that linear algebraic PE can also be extended to accommodate Or-rules. Moreover, we propose using eigendecomposition and Jordan normal form to conduct PE in vector spaces. We compare the proposed techniques on a set of acyclic and cyclic logic programs to evaluate their effectiveness. It is shown that the iteration method for PE, especially with sparse format, is the most efficient one in general cases. However, the decomposition method has the potential for future research to leverage eigenvalues and eigenvectors of program matrices for reasoning.

Full Paper (PDF 453K)

Slide