Recursion equation sets computing logic programs (Q920624)

This paper deals with the semantics of the pure Horn-logic basis for logic programs. The meaning of such programs can be described as the least fixed point of a relation-valued mapping over the Herbrand universe generated by the constants and function symbols occuring in the program. The author investigates methods for expressing these recursion equations over a more suitable domain: finite and infinite sequences of ground atoms, relating in this way the computation of a logic program with a dataflow like computation over ground atoms. In order to deal with the involved nondeterminism one more tool is required: the availability of fair merge functions which ensure that every part of some input among a set of inputs will sooner or later be represented to the functionals expressing the inferences stated in the program. The result is a system of monotone continuous recursive equations over the sequence domain the least fixed point of which can be shown to faithfully represent the minimal Herbrand model of the original program. The recursion equation can be expressed in a Lisp-like fashion. The author doesn't comment on the advantages of this approach over the traditional relational framework for obtaining the minimal Herbrand model. It is only indicated that the approach is insufficient for turning logic programs into equivalent functional programs. For your reviewer it is unclear whether there exist any such advantages at all.