Enhancing Linear Algebraic Computation of Logic Programs Using Sparse Representation
Tuan Nguyen Quoc, Katsumi Inoue, and Chiaki Sakama
New Generation Computing. vol. 40(1), pages 225-254 (2022)
Algebraic characterization of logic programs has received increasing attention in recent years.
Researchers attempt to exploit connections between linear algebraic computation and symbolic computation in order to
perform logical inference in large scale knowledge bases.
In this paper, we analyze the complexity of the linear algebraic methods
for logic programs and propose further improvement by using sparse matrices to embed logic programs in vector spaces.
We show its great power of computation in reaching the fixed-point of the immediate consequence operator. In particular,
performance for computing the least models of definite programs is dramatically improved using the sparse matrix
representation.We also apply the method to the computation of stable models of normal programs, in which the guesses
are associated with initial matrices, and verify its effect when there are small numbers of negation. These results show
good enhancement in terms of performance for computing consequences of programs and depict the potential power of
tensorized logic programs.