Extending Homeomorphic Embedding in the Context of Logic Programming

Recently well-quasi orders in general, and homeomorphic embedding in particular, have gained popularity to ensure the termination of program analysis, specialisation and transformation techniques. However, as we illustrate in the paper, the homeomorphic embedding relation as it is usually defined suffers from several inadequacies which make it less suitable in a logic programming context. We present several increasingly refined ways to remedy this problem by providing more sophisticated treatments of variables and present a new, extended homeomorphic embedding relation. 1 Introduction The problem of ensuring termination arises in a lot of different contexts in computer science. For instance a lot of work has been devoted to proving termination of term rewriting systems (e.g. [7] and references therein) or of logic programs (e.g. [5, 38] and references therein). It is also an important issue within all areas of program analysis, specialisation and transformation: one usually strives fo..