Proving Termination of Logic Programs by Exploiting Term Properties

In this paper semi-linear norms, a class of functions to weight the terms occurring in a program, are defined and studied. All the functions in this class have the nice property of allowing a syntactical characterization of rigid terms, that is terms whose weight does not change under substitution. Based on these norms, a general proof method for termination of pure Prolog programs can be adapted to deal with a large class of programs in a simple way. The simplified method requires pre/post specifications well-behaved with respect to substitutions, quite a general case in practice, and ordering functions not increasing with respect to substitutions, which can be based on semi-linear norms, to be associated to program predicates. A few examples of this simplified proof method are given