A New Algorithm for Computing Least Generalization of a Set of Atoms

Hien D. Nguyen and Chiaki Sakama

in: Proceedings of the 29th International Conference on Inductive Logic Programming (ILP 2019), Lecture Notes in Artificial Intelligence 11770, pages 81-97, Springer-Verlag, 2019.


This paper provides a new algorithm of computing a least generalization of a set of atoms. Our algorithm is based on the notion of anti-combination that is the inverse substitution of a combined substitution. In contrast to an anti-unification algorithm that computes a least generalization of two atoms, anti-combination can compute a least generalization of (more than two) atoms in parallel. We evaluate the proposed algorithm using randomly generated data and show that anti-combination outperforms the iterative application of an anti-unification algorithm in general.

Full Paper (PDF 1220K) Slide