Computing Logic Programming Semantics in Linear Algebra

Hien D. Nguyen, Chiaki Sakama, Taisuke Sato and Katsumi Inoue

in: Proceedings of the 12th International Conference on Multi-disciplinary Trends in Artificial Intelligence (MIWAI 2018), Lecture Notes in Artificial Intelligence 11248, Springer-Verlag, pages 32-48, 2018.


Logic programming is a logic-based programming paradigm, and provides languages for declarative problem solving and symbolic reasoning. In this paper, we develop new algorithms for computing logic programming semantics in linear algebra. We first introduce an algorithm for computing the least model of a definite logic program using matrices. Next, we introduce an algorithm for computing stable models of a normal logic program. We also develop optimization techniques for speeding-up those algorithms. Finally, the complexity of them is analyzed and tested in practice.

Full Paper (PDF 747K) Slide