In this paper we introduce the basic concepts behind the problem of proving program termination, including well-founded relations, well-ordered sets, and ranking functions. We also connect the notion of termination of computer programs with that of well-founded relations. This paper introduces no original concepts, nor does it propose solutions towards the the problem of automating termination proofs. It does, however, provide a foundation from which the reader can peruse the more advanced literature on the topic.
IOS Press, Inc.
6751 Tepper Drive
Clifton, VA 20124
Tel.: +1 703 830 6300
Fax: +1 703 830 2300 firstname.lastname@example.org
(Corporate matters and books only) IOS Press c/o Accucoms US, Inc.
For North America Sales and Customer Service
West Point Commons
Lansdale PA 19446
Tel.: +1 866 855 8967
Fax: +1 215 660 5042 email@example.com