Termination Analysis of CHR Revisited

摘要

Today, two distinct direct approaches to prove termination of CHR programs exist. The first approach, by T. Friihwirth, proves termination of CHR programs without propagation. The second, by Voets et al., deals with programs that contain propagation. It is however less powerful on programs without propagation. In this paper, we present new termination conditions that are strictly more powerful than those from previous approaches and that are also applicable to a new class of programs. Furthermore, we present a new representation for CHR states for which size-decreases between consecutive states correspond to termination. Both contributions are linked: our termination conditions correspond to the existence of a well-founded order on the new state representation, which decreases for consecutive computation states.