THE LATTICE OF FLOW DIAGRAMS

Abstract

This paper represents a continuation of the program sketched in Outline of a Mathematical Theory of Computation (PRG02), The language under consideration is the elementary language of flow diagrams where the level of analysis concerns the flow of control but not any questions of storage, assignment, block structure or the use of parameters. A new feature of the approach of this paper is the treatment of both syntax and semantics with the aid of complete lattices. This provides considerable unification of methods (especially in the use of recursive definitions) which can be applied to other languages. The main emphasis of the paper is on the method of semantical definition, and though the notion of equivalence of diagrams is touched upon a full algebraic formulation remains to be done.