main-content

## Über dieses Buch

Cal Elgot was a very serious and thoughtful researcher, who with great determi­ nation attempted to find basic explanations for certain mathematical phenomena­ as the selection of papers in this volume well illustrate. His approach was, for the most part, rather finitist and constructivist, and he was inevitably drawn to studies of the process of computation. It seems to me that his early work on decision problems relating automata and logic, starting with his thesis under Roger Lyndon and continuing with joint work with Biichi, Wright, Copi, Rutledge, Mezei, and then later with Rabin, set the stage for his attack on the theory of computation through the abstract treatment of the notion of a machine. This is also apparent in his joint work with A. Robinson reproduced here and in his joint papers with John Shepherdson. Of course in the light of subsequent work on decision problems by Biichi, Rabin, Shelah, and many, many others, the subject has been placed on a completely different plane from what it was when Elgot left the area. But I feel that his papers, results-and style-were very definitely influential at the time and may well have altered the course of the investigation of these problems. As Sammy Eilenberg explains, the next big influence on Elgot's thinking was category theory, which gave him a way of expressing his ideas in a sharply algebraic manner. The joint book with Eilenberg is one illustration of this influence.

## Inhaltsverzeichnis

### Realization of Events by Logical Nets

Abstract
In Representation of Events in Nerve Nets and Finite Automata [3], S. C. Kleene obtains a number of interesting results. The most important of these, his analysis and synthesis theorems (theorems 5 and 3), are obscured both by the complexity of his basic concepts and by the nature of the elements used in his nets. In this paper we give a new formulation and new proofs of Kleene’s analysis and synthesis theorems, in which we presuppose no acquaintance with Kleene’s work. We use simpler basic concepts and construct our nets out of more familiar and convenient elements (see section 4). The simplified formulation and proofs should make these important results more widely accessible. Some detailed comments on Kleene’s ideas are made in section 7.
Irving M. Copi, Calvin C. Elgot, Jesse B. Wright

### Random-Access Stored-Program Machines, an Approach to Programming Languages

Abstract
A new class of machine models as a framework for the rational discussion of programming languages is introduced. In particular, a basis is provided for endowing programming languages with semantics. The notion of Random-Access Stored-Program Machine (RASP) is intended to capture some of the most salient features of the central processing unit of a modern digital computer. An instruction of such a machine is understood as a mapping from states (of the machine) into states. Some classification of instructions is introduced. It is pointed out in several theorems that programs of finitely determined instructions are properly more powerful if address modification is permitted than when it is forbidden, thereby shedding some light on the role of address modification in digital computers. The relation between problem-oriented languages (POL) and machine languages (ML) is briefly considered.
Calvin C. Elgot, Abraham Robinson

### Abstract Algorithms and Diagram Closure

Abstract
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.
Calvin C. Elgot

### Algebraic Theories and Program Schemes

Abstract
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.
Calvin C. Elgot

### The Common Algebraic Structure of Exit-Automata and Machines

Summary
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.
Calvin C. Elgot

### Monadic Computation and Iterative Algebraic Theories

Abstract
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’.
Calvin C. Elgot

### On the Algebraic Structure of Rooted Trees

Abstract
Many kinds of phenomena are studied with the aid of (rooted) digraphs such as those indicated by Figs. 1.1 and 1.2. The two digraphs, while different, usually represent the same phenomenon, say, the same “computational process.” Our interest in rooted trees stems from the fact that these two digraphs “unfold” into the SAME infinite tree. In some cases at least it is also true that different (i.e. non-isomorphic) trees represent different phenomena (of the same kind). In these cases the unfolding (i.e. the trees) are surrogates for the phenomena.
Calvin C. Elgot, Stephen L. Bloom, Ralph Tindell

### Solutions of the Iteration Equation and Extensions of the Scalar Iteration Operation

Abstract
We study the solutions to a (vector) equation somewhat analogous to the traditional equations of linear algebra. Whereas, in introductory linear algebra the domain of discourse is the field of real numbers (or an arbitrary field) our domain of discourse is the algebraic theory of (multi-rooted, leaf-labeled) trees (or, more generally, any iterative theory).
As in linear algebra, we obtain a necessary and sufficient condition for our equations to have unique solutions and we can describe “parametrically” the totality of solutions. However, whereas in linear algebra, there is no way of giving 1 ÷ 0 meaning in such a way that all the “old laws” hold, we can give meaning to the “iteration operation” (the analogue of division into 1) in such a way that all the “old laws” still hold. Indeed, we can describe “parametrically” all such ways of extending the (partially defined) scalar iteration operation to all trees (more generally, morphisms).
Stephen L. Bloom, Calvin C. Elgot, Jesse B. Wright

### Vector Iteration in Pointed Iterative Theories

Abstract
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 main result shows that the vector iterate g in (J, ⊥) satisfies the equation g = (g ), where g is a nonsingular morphism simply related to g (so that (g ) is the unique solution of the iteration equation for g ).
In the case that J = ΓTr, the iterative theory of Γ-trees, it is shown that the vector iterate g + in (J, ⊥) is a metric limit of “modified powers” of g.
Stephen L. Bloom, Calvin C. Elgot, Jesse B. Wright

### Structured Programming With and Without GO TO Statements

Abstract
While “Dijkstra flow-chart schemes” (built out of assignment statement schemes by means of composition, if-then and whiledo) are simple and perspicuous, they lack the descriptive power of flow-chart schemes (provided additional “variables” are not permitted). On the other hand, the analogous multiexit composition binary alternation-conditional iteration (CACI) schemes introduced below, which are virtually as simple and perspicuous as Dijkstra schemes, describe exactly the same computational processes as flow-chart schemes (without the aid of additional variables).
Theorem 9.1 makes contact with “reducible flow-graphs” an active area in its own right.
Calvin C. Elgot

### A Semantically Meaningful Characterization of Reducible Flowchart Schemes

Abstract
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.
Calvin C. Elgot, John C. Shepherdson

### An Equational Axiomatization of the Algebra of Reducible Flowchart Schemes

Abstract
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)

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.
The equational axioms referred to in the title relate ≈-identified (i.e. isomorphism-identified) flowchart schemes by these three operations. The structure freely generated by the set Γ of atomic flowchart schemes is Γ Red, the theory (or multi-sorted algebra) of reducible flowchart schemes. The axioms involving only + and ∘ yield ΓAc, the theory of accessible, acyclic flowchart schemes. Semantical domains which may be used to interpret Γ Red also satisfy these axioms. The set of equational statements true for Γ Red (which are also logical consequences of the axioms) determine a congruence on the algebra of expressions built out of Γ, Sur, +, ∘ and † whose quotient is another description of Γ Red.
Thus the expressions built up using these three operations provide an alternative notation for reducible flowchart programs; the purpose of the axioms is to determine when two expressions represent the same schematic program.
A similar statement holds for ΓAc.
Calvin C. Elgot, John C. Shepherdson

### On Coordinated Sequential Processes

Abstract
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.
Calvin C. Elgot, Raymond E. Miller

Without Abstract
Calvin C. Elgot

### Backmatter

Weitere Informationen