Search

The flowchart schemes called “reducible” are of interest because (1) they schematize programs without “go to” statements; (2) for every flowchart scheme there is a reducible one which is step-by-step equivalent to it; (3) they manipulate readily. The reducible flowchart schemes admit both graph-theoretic and algebraic descriptions. A flowchart scheme F with n begins and p exits is reducible iff both (a) for every vertex v there is a begin-path (i.e. a path from a begin vertex) which ends in v (b) for every closed path C there is a vertex vC of C such that every begin path to a vertex of C meets vC. Algebraically: F is reducible iff it can be built up from atomic flowchart schemes (which may be thought of as corresponding to single instructions) and surjective trivial flowchart schemes (which may be thought of as redirecting flow of control) by means of composition (∘), separated pairing (+), and scalar iteration (†). Dropping † yields the accessible, acyclic flowchart schemes.

This paper is a sequel to a previous paper S. L. Bloom, C. C. Elgot and J. B. Wright, Solutions of the iteration equation and extensions of the scalar iteration operations, SIAM J. Comput., 9 (1980), pp. 25–45. In that paper it was proved that for each morphism ⊥: 1 → 0 in an iterative theory J there is exactly one extension of the scalar iteration operation in J to all scalar morphisms such that \( I_1^{ + } = \bot \) and all scalar iterative identities remain valid. In this paper the scalar iteration operation in the pointed iterative theory (J, ⊥) is extended to vector morphisms while preserving all the old identities.

The notion algebraic theory was introduced by Lawvere in 1963 (cf. S. Eilenberg and J. B. Wright, Automata in general algebras, Information and Control 11 (1967) 4) to study equationally definable classes of algebras from a more intrinsic point of view. We make use of it to study Turing machines and machines with a similar kind of control at a level of abstraction which disregards the nature of ‘storage’ or ‘external memory’.

A notion, of “exit-automaton” is introduced to play a role analogous to “machine scheme” or “program scheme”. Exit-automata and machines are equipped with algebraic structure leading to a simple characterization of their behaviors.

The mutual exclusion problem introduced (as far as we know) by Dijkstra in 1965 is intriguing because on the one hand it appears to be typical of a broad class of important systems problems and on the other poses difficult problems of mathematization. There has been extensive attention to this (and other synchronization problems) since that date. Nevertheless our approach to the problem differs from all the others in at least two important ways. First: we take the problem to be “construct from n uncoordinated sequential processes, n coordinated ones which satisfy (1) mutual exclusion, (2) fairness and (3) simulation.” Second: our mathematical model can directly represent simultaneous actions. Since we do not constrain the synchronization in some of the usual ways, however, the realm of possible solutions is much broader than considered elsewhere. The main solution we offer is simple in that each process need read only one binary variable (or register), viz. its own, and write in one, viz. its neighbor’s. The emphasis of our approach is in the mathematical formulation of the problem, and the proof that the solution satisfies the desired properties, rather than in the novelty of the solution itself. The other solutions offered serve to emphasize the enormous differences in implementation associated with what we call the “conceptual solution,” and the fact that instructions (or atomic actions) don’t compose i.e. a sequence of two (single entry — single exit) instructions of a process is not system equivalent to any single instruction. Contrary to many other solutions to the mutual exclusion problem, the solutions given here do not employ a test and set primitive i.e. an indivisible test and set instruction.

A programming language L presumably should be designed, at least in part, to express algorithms of a given class M. Given an algorithm in the class M, there should be a name in L which expresses it. In addition, L should possess names for the “tasks performable by algorithms” in M. A theory of the language L should presumably include statements about algorithms in M and their tasks.

A “scalar” flowchart scheme, i.e. one with a single begin “instruction” is reducible iff its underlying flowgraph is reducible in the sense of Cocke and Allen or Hecht and Ullman. We characterize the class of reducible scalar flowchart schemes as the smallest class containing certain members and closed under certain operations (on and to flowchart schemes). These operations are “semantically meaningful” in the sense that operations of the same form are meaningful for “the” functions (or partial functions) computed by interpreted flowchart schemes; moreover, the schemes and the functions “are related by a homomorphism.” By appropriately generalizing “flowgraph” to (possibly) several begins (i.e. entries) we obtain a class of reducible “vector” flowchart schemes which can be characterized in a manner analogous to the scalar case but involving simpler more basic operations (which are also semantically meaningful). A significant side effect of this semantic viewpoint is the treatment of multi-exit flowchart schemes on an equal footing with single exit ones.

The objective of this paper is to point out that the “semantics” of cycle-free program schemes (of the kind intuitively described in Section 2) may be explicated by existing algebraic notions. More explicitly, equivalence classes of schemes correspond to morphisms in a free algebraic theory (cf., Lawvere (1963), and Eilenberg and Wright (1967)), and an interpretation of the collection of morphisms is a coproduct-preserving functor into an appropriate target category.