USING ATMS TO EFFICIENTLY VERIFY THE TERMINATION OF REWRITE RULE PROGRAMS
Masahito Kurihara, Hisashi Kondo, Azuma Ohuchi · International Journal of Software Engineering and Knowledge Engineering · 1992
Assumption-based truth maintenance systems (ATMS) have become powerful and widely used tools in artificial intelligence problem solvers. In this paper, we apply ATMS to verification of termination of computer programs written as a set of rewrite rules. Compared with the traditional methods based on the ordinary backtracking, our method can greatly improve the overall efficiency by virtue of the ATMS's ability to avoid futile backtracking, rediscovering inferences, and rediscovering contradictions. The originality of our work lies in the practical use of the ATMS in a software engineering problem and in the communication protocol between the termination verifier and the ATMS.