Abstract
A persistent data structure enables several versions to coexist, sharing a common history, i.e. common ancestors, whereas an ephemeral structure only gives access to the most recent version.
This presentation introduces the notion of a semi-persistent structure, where access is limited to the ancestors of the most recent version. A semi-persistent structure is particularly suited to a traceback algorithm. Several examples of semi-persistent structures are presented, and the savings in time and space are illustrated.
To guarantee the correct use of a semi-persistent structure, we adopt a deductive approach in which logical annotations in the program express the kinship relations between versions of the structure. A decision procedure is given for the resulting proof obligations.
