Search

1. Motivation. Many variants of the notion of automaton have appeared in the literature. We find it convenient here to adopt the notion of E. F. Moore [7]. Inasmuch as Rabin-Scott [9] adopt this notion, too, it is convenient to refer to [9] for various results presumed here. In particular, Kleene's theorem [5, Theorems 3, 5] is used in the form in which it appears in [9]. It is often perspicacious to view regular expressions, and this notion is used in the sense of [3]. In general, we are concerned with the problems of automatically designing an automaton from a specification of a relation which is to hold between the automaton's input sequences and determined output sequences. These "design requirements" are given via a formula of some kind. The problems with which we are concerned have been described in [1]. With respect to particular formalisms for expressing "design requirements" as well as the notion of automaton itself, the problems are briefly and informally these: (1) to produce an algorithm which when it operates on an automaton and a design requirement produces the correct answer to the question "Does this automaton satisfy this design requirement?", or else show no such algorithm exists; (2) to produce an algorithm which operates on a design requirement and produces the correct answer to the question "Does there exist an automaton which satisfies this design requirement?", or else show no such algorithm exists; (3) to produce an algorithm which operates on a design requirement and terminates with an automaton which satisfies the requirement when one exists and otherwise fails to terminate, or else show no such algorithm exists. Interrelationships among problems (1), (2), (3) will appear in the paper [1]. This paper will also indicate the close connection between problem (1) and decision problems for truth of sentences of certain arithmetics. The paper [1 ] will also make use of certain results concerning weak arithmetics already obtained in the literature to obtain answers to problems (1) and (3). Thus

In ''Monadic Computation and Iterative Algebraic Theories'' by Calvin C. Elgot,the notion ''iterative theory'' (more fully, ''ideal theory closed under conditional iteration'') is introduced and applied to the study of computational processes. The main point of the present paper is to show the existence (in a constructive sense) of free iterative theories. The main complication is the fact that in an iterative theory I the ''iteration'' operation is not defined for all elements of I. Were it not for this complication, the existence of free iterative theories would follow from general algebraic considerations (extended to many-sorted algebras). Actually we sketch two proofs of the existence of free iterative theories. One argument follows as much as possible general algebraic lines and is given a linguistic flavor in order to emphasize the concreteness of the ideas involved. The second argument depends upon ''normal descriptions'': a morphism in the free iterative theory being an equivalence class of normal descriptions.

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.

A threshold function is a mapping from {0, 1}n into {0, 1} satisfying: there exists integers w1, w2,..., wn, t such that f(x1, x2,..., xn) = 1 iff Sigmai=1n wi xi \geq t. Two chains of conditions necessary for a function to be a threshold function are discussed. Early parts of the two chains are equivalent. One chain constitutes a sufficient condition while it is not known whether the other more intrinsic condition is sufficient or not. It is shown that any set of threshold functions of n variables realizable by a common set of weights is included in a maximal chain of threshold functions of length 1 + 2n realizable by a common set of weights. If f depends on at most 5 variables or if f or its dual has at most 4-prime implicants, then f is a threshold function iff it is 2-monotonic.