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 \div 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).

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 $ \bot :1 \to 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^\dag = \bot $ and all scalar iterative identities remain valid. In this paper the scalar iteration operation in the pointed iterative theory $(J, \bot )$ is extended to vector morphisms while preserving all the old identities. The main result shows that the vector iterate $g^\dag $ in $(J, \bot )$ satisfies the equation $g^\dag = (g_ \bot )^\dag $, where $g_ \bot $ is a nonsingular morphism simply related to g (so that $(g_ \bot )^\dag $ is the unique solution of the iteration equation for $g_ \bot $). In the case that $J = \Gamma {\text{Tr}}$, the iterative theory of $\Gamma $-trees, it is shown that the vector iterate $g^\dag $ in $(J, \bot )$ is a metric limit of “modified powers” of g.

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

We study certain first and second order theories which are semantically defined as the sets of all sentences true in certain given structures. Let be a structure where A is a non-empty set, λ is an ordinal, and Pα is an n(α)-ary relation or function4 on A. With we associate a language L appropriate for which may be a first or higher order calculus. L has an n(α)-place predicate or function constant P for each α < λ. We shall study three types of languages: (1) first-order calculi with equality; (2) second-order monadic calculi which contain monadic predicate (set) variables ranging over subsets of A; (3) restricted (weak) second-order calculi which contain monadic predicate variables ranging over finite subsets of A.

Finite automata which communicate with counters or with tapes on a single letter alphabet with end mark are studied.A typical machine system s~udied here consists of a family of machines; the finite automaton part of each of the machines is ideutical; each machine has one reset counter (Mmost blank loop tape) and one non-reset counter (ahnost blank straight tape) ; the first counter counts up to a, say, and the second comets up to b.For each pair of natural numbers a, b there is a machine of the system with counters running up to a, b respectively.The system "accepts" those pairs (a, b) such that the (a, b)-nmchine eventually halts, when started in standard position.Thus the system de* fines a binary relation on natural numbers.Some solvability and unsolvability results are obtained concerning the emptiness of the set accepted by a system or the emptiness of the intersection of the sets accepted by two or more systems.Some of the theorems strengthen results of Rabin and Scott [8].It is shown for a certain class of systems that the relations defined by them are exactly the same as those definable in the elementary theory of addition of natural numbers.For another class of systems it is shown that an intersection problem is equivalent to Hilbert's tenth problem.

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.

article Free AccessRealization of Events by Logical Nets Authors: Irving M. Copi University of Michigan, Ann Arbor, Mich. University of Michigan, Ann Arbor, Mich.View Profile , Calvin C. Elgot University of Michigan, Ann Arbor, Mich. University of Michigan, Ann Arbor, Mich.View Profile , Jesse B. Wright University of Michigan, Ann Arbor, Mich. University of Michigan, Ann Arbor, Mich.View Profile Authors Info & Claims Journal of the ACMVolume 5Issue 2April 1958 pp 181–196https://doi.org/10.1145/320924.320931Published:01 April 1958Publication History 75citation572DownloadsMetricsTotal Citations75Total Downloads572Last 12 Months39Last 6 weeks9 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

A basic formulation and a solution are advanced for the problem as to which electronic computer design is the best, that with a multiple or that with a single address system. Generally from a statistical point of view, fewer words are required to code by means of an idealize single address than by a triple address.