Unification with lazy non-redundant copying

Abstract

This paper presents a unification procedure which eliminates the redundant copying of structures by using a lazy incremental copying approach to achieve structure sharing. Copying of structures accounts for a considerable amount of the total processing time. Several methods have been proposed to minimize the amount of necessary copying. Lazy Incremental Copying (LIC) is presented as a new solution to the copying problem. It synthesizes ideas of lazy copying with the notion of chronological dereferencing for achieving a high amount of structure sharing.