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.
Abstract
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