Extending Homeomorphic Embedding in the Context of Logic Programming 

by Michael Leuschel 
K.U. Leuven, Belgium

Abstract 

Recently well-quasi orders in general, and homeomorphic embedding in particular, have gained 
popularity to ensure the termination of program analysis, specialisation and transformation tech-
niques. However, as we illustrate in the paper, the homeomorphic embedding relation as it is usu-
ally 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 rela-
tion.