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

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.