In an earlier paper Walters introduced a family of imperative programming languages based on concepts from distributive categories. The development in that, and in a subsequent paper by Walters and Khalil, was carried out within the category Set of s

Our earlier work on abstract data types is extended by the answers to a number of questions on the power and limitations of algebraic specification techniques and by an algebraic treatment of parameterized data types like sets-of-( ) and stacks-of-().The "hidden function" problem (the need to include operations in specifications which are wanted hidden from the user) is investigated; the relative power of conditional specifications and equational specifications is investigated; and it is shown that parameterized specifications must contain "side conditions" (e.g., that finite-sets-of-d requires an equality predicate on d).

This paper extends our earlier work on abstract data types by providing an algebraic treatment of parametrized data types (e.g., sets-of-(), stacks-of-(), etc.), as well as answering a number of questions on the power and limitations of algebraic specification techniques. In brief: we investigate the “hidden function” problem (the need to include operations in specifications which we want to be hidden from the user); we prove that conditional specifications are inherently more powerful than equational specifications; we show that parameterized specifications must contain “side conditions” (e.g., that finite-sets-of-d requires an equality predicate on d), and we compare the power of the algebraic approach taken here with the more categorical approach of Lehman and Smyth.

Many apparently divergent approaches to specifying formal semantics of programming languages are applications of initial algebra semantics. In this paper an overview of initial algebra semantics is provided. The major technical feature is an initial continuous algebra which permits unified algebraic treatment of iterative and recursive semantic features in the same framework as more basic operations.

In a wide variety of situations, computer science has found it convenient to define complex object as (fixed-point) solutions of certain equations. This has been done in both algebraic and order-theoretic settings, and has often been contrasted with other approaches. This paper shows how to formulate such solutions in a setting which encompasses both algebraic and order-theoretic aspects, so that the advantages of both worlds are available. Moreover, we try to show how this is consistent with other approaches to defining complex objects, through a number of applications, including: languages defined by context-free grammars; flow charts and their interpretations; and monadic recursive program schemes. The main mathematical results concern free rational theories and quotients of rational theories. However, the main goal has been to open up what we believe to be a beautiful and powerful new approach to the syntax and semantics of complex recursive specifications.

This paper gives an informal presentation of constructions which, when combined, enable one to construct high level programming languages from algebras or, equivalently, from collections of primitive operations on some set (e.g. from the arithmetic, vector and logical operations on the set of integers, integer vectors, and truth values). Using this approach one can construct languages with block structure, procedures, procedure calls by both name and value, plus essentially simpler concepts such as assignment statements and conditional transfers. The constructions are algebraic in the sense that they are constructions on algebras which yield new algebras. However, for the sake of comprehensibility, we present them in this paper in a more informal manner as constructions on “black boxes”. This paper is a continuation of work presented earlier in [3] and [4] and owes much to the joint work to be reported in [5].

This is the introductory paper in a series devoted to a general algebraic theory of “recursive definitions” and “recursive languages”. In this paper we present the fundamental concepts and theorems concerning the basic structure (basic syntax), the semantics and the combination and manipulation of “recursive definitions” and the closure properties of “recursive languages”. The development is carried out within the framework of category theory and lattice theory. To illustrate the generality of the approach and our results we show how they apply directly to the specific examples of “recursive languages” of (generalized) context-free grammars, Turing machines, and flowcharts.

In the last fifteen years many researchers working in such diverse areas as pattern recognition, parallel computation, self-reproducing automata, pattern recognition, evolution theory, information retrieval, and integrated circuit technology have found it convenient to use an array of identical intercommunicating finite-state machines as their underlying model. This naturally suggests that it would be worthwhile to develop a comprehensive theory of such arrays which would then provide a common framework for all these areas. Yamada and Amoroso have taken up this suggestion, and this paper is the first in a proposed series of papers reporting their results. However, as they readily admit, they have not attempted to produce a truly comprehensive model (an ill-defined, if not impossible, task), but rather they have been concerned with a "fairly general" model based largely on the earlier work of Moore.

A modular computer may be informally defined to be a device consisting of a large (or infinite) number of identical circuit modules connected together in some uniform manner. This paper is concerned with making the concept of ``connected together in a uniform manner'' mathematically precise. Uniformity of connection in a modular device is first defined in terms of the linear graph whose vertices correspond to the modules and whose edges correspond to the cables connecting them. It is shown that the class of graphs satisfying the definition is precisely the class of group-graphs; that is, the vertices correspond to the elements of a group G, and there is a finite subset G0of G' (1 ∉ G0) such that {g, g'} is an edge of the graph if, and only if, there exists g0in G0such that g'. = gg0. It is then shown that restricting the group G to be Abelian restricts the patterns of simultaneous activity which may occur within the computer.