COMPUTATION GRAPHS

Abstract

The notion of a computation graph is introduced. A computation graph is a rooted, directed graph whose nodes are labelled by statements (instructions) to be executed. The motivation for developing computation graphs comes from a desire to represent programs by well‐defined, manipulable structures and to permit search (especially backtracking) to be a natural part of the execution of such programs. This initial work considers very simple computation graphs where the only statements that can be executed are assignment statements and tests. Procedure calls, parameter passing, etc. are not considered. The execution rule for computation graphs is based upon search procedures. The computation rule presented permits a computation graph to be executed depth first, breadth first or using a combination of both. This is done by defining functions, which are arguments to the computation rule, to control the traversal of the graph. The use of the rule is illustrated by describing functions to permit the rule to execute the same graph depth first and breadth first.

Citation

BAUER, M.A. (1976), "COMPUTATION GRAPHS", Kybernetes, Vol. 5 No. 1, pp. 49-54. https://doi.org/10.1108/eb005408