Recursion equation sets computing logic programs
type: Item
instance of: scholarly article
title: Recursion equation sets computing logic programs
zbMATH Open document ID: 0708.68035
DOI: 10.1016/0304-3975(90)90023-B
author: Susumu Yamasaki
published in: Theoretical Computer Science
publication date: 1990-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68Q55
Mathematics Subject Classification ID: 68N17
Mathematics Subject Classification ID: 03B70
zbMATH DE Number: 4164147
zbMATH Keywords: logic programs
zbMATH Keywords: Herbrand domain
zbMATH Keywords: Horn-logic
zbMATH Keywords: least fixed point
reviewed by: Peter van Emde Boas
MaRDI profile type: Publication
cites work: Q3221399
cites work: Contributions to the Theory of Logic Programming
cites work: Lucid—A Formal System for Writing and Proving Programs
cites work: The Semantics of Predicate Logic as a Programming Language
cites work: A deterministic prolog fixpoint semantics
cites work: Q3732937
cites work: Q4054644
cites work: Closures and fairness in the semantics of programming logic
cites work: Optimal fixedpoints of logic programs
cites work: Q3042377
cites work: Q4187284
cites work: A fixpoint semantics of Horn sentences based on substitution sets
Recommended article: Algebra and Coalgebra in Computer Science
Recommended article: Recursion Equations as a Programming Language
Recommended article: Q3432595
Recommended article: Logic Programs for Primitive Recursive Sets
Recommended article: The logic of recursive equations
Recommended article: Q4852240
Recommended article: Q3635984
Recommended article: Q4036550
Recommended article: Logic programming with equations
Recommended article: Q3727354
description: scientific article; zbMATH DE number 4164147