scientific article; zbMATH DE number 3924108

From MaRDI portal
Publication:3698285





[For the entire collection see Zbl 0562.00009.] Two approaches are examined in order to provide proof rules for the termination of PROLOG programs. The motivation for the rules is both to provide a non-operational semantic definition for liveness properties of the language, and to allow proving the termination of given programs. The first approach to proving termination is global in that the entire state, including the history, is available at all times. Assertions are made about that state by using a descending variant function to a well-founded set. Techniques which have been useful in designing termination proof- rules for nondeterministic and parallel programs with fairness assumptions are employed. The second approach presented is compositional and modular, and does not assume an available global environment. This view requires assertions and proof rules involving streams of input and output from procedures. A new assertion language about streams is introduced in this context. It should be noted that the semantic framework suggested by \textit{K. R. Apt} and \textit{M. H. van Emden} in J. Assoc. Comput. Mach. 29, 841-862 (1982; Zbl 0483.68004) is not sufficient to capture the termination aspects of PROLOG, and thus is an inadequate base for the soundness and completeness proofs needed for the suggested rules. The concept of state in the article is also inadequate, and the authors are presently at work on a new semantics which can be used for proving the soundness and completeness of the given rules.











This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3698285)