From 3-valued Semantics to Supported Model Computation for Logic Programs in Vector Spaces

Taisuke Sato, Chiaki Sakama and Katsumi Inoue

Proceedings of the 12th International Conference on Agents and Artificial Intelligence (ICAART), pages 758-765, Malta, 2020.


We propose a linear algebraic approach to computing 2-valued and 3-valued completion semantics of finite propositional normal logic programs in vector spaces. We first consider 3-valued completion semantics and construct the least 3-valued model of comp(DB), i.e. the iff (if-and-only-if) completion of a propositional normal logic program DB in Kleene's 3-valued logic which has three truth values {t(true), f(false), ⊥(undefined)}. The construction is carried out in a vector space by matrix operations applied to the matricized version of a dualized logic program DBd of DB. DBd is a definite clause program compiled from DB and used to compute the success set P∞ as true atoms and finite failure set N∞ as false atoms that constitute the least 3-valued model I∞ = (P∞,N∞) of comp(DB). We then construct a supported model of DB, i.e. a 2-valued model of comp(DB) by carefully assigning t or f to undefined atoms not in P∞ or N∞ so that the resulting model is 2-valued and supported. The assigning process is guided by an atom dependency relation on undefined atoms. We implemented our proposal by matrix operations and conducted an experiment with random normal logic programs which demonstrated the effectiveness of our linear algebraic approach to computing completion semantics.

Full Paper (PDF 182K) Slide