Equational Dataflow Programs Computing Logic Programs


IEICE TRANSACTIONS (1976-1990)   Vol.E71   No.11   pp.1134-1139
Publication Date: 1988/11/25
Online ISSN: 
Print ISSN: 0000-0000
Type of Manuscript: PAPER
Category: Automaton, Language and Theory of Computing

Full Text: PDF>>
Buy this Article

In this paper we give a method of transforming logic programs into equational dataflow programs. The equational dataflow program is a set of recursion equations as to variables over a sequence domain. A recursion equation corresponds to each definite (Horn) clause which is interpreted as a transformation of variables to a variable. Each variable denotes a function from the set of natural numbers to the Herbrand base, that is, a sequence of ground atoms. The fair merge function is necessary to realize OR-nondeterminism, which is essential in the deductions of logic programs, by means of an equational dataflow program. The nondeterminism in the transformation caused by a definite clause is eliminated and ensured fair by introducing a kind of oracle which will also be provided by simple recursion equations. Then it will be shown that the equational dataflow program with the oracle is both sound and complete in denoting the finite computation of the original logic program. The semantics of the equational dataflow program is given by fixpoint approach and is interpreted as a semantics of the given logic program.