A transformational method for proving termination of logic programs

From MaRDI portal





The paper proposes a transformational approach to the termination problem of well-model logic programs by reducing it to termination in term rewriting systems. A well-moded logic program is made up only of well- moded clauses, in which the producer-consumer relation is acyclic and every variable in a clause has a producer. The algorithm consists of two steps: (a) to transform the given well-moded logic program into a rewrite system, and (b) to prove the termination of the rewrite system using the various available techniques in this field. The transformation is purely syntactical and easy mechanizable, requires no preprocessing, and is applicable to a larger class of logic programs, namely such programs can be handled that violate the properties of uniqueness and existence of admissible solution graph, or contain mutual recursion. The method was successfully applied for showing termination of the Prolog implementation of compiler for ProCoS level \(O\) language \(\text{PL}_ 0\) developed at Oxford University. For the entire collection see [Zbl 0772.68004].











This page was built for publication: A transformational method for proving termination of logic programs

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