A description is given of language constructs for specifying concurrency in CDL*. The main goals in designing the language have been: modular specification, data integrity, and expressiveness. The language constructs are presented, and it is shown through examples how the constructs mirror the goals. The major advantages of the constructs are as follows: (1) data integrity is achieved without resorting to mutual exclusion unnecessarily, (2) dynamic resource management is achieved safely guaranteeing the anonymity of the dynamically allocating resources, and (3) similar components can be packaged together without resorting to sequential access. Various features of the language are illustrated through examples. In short, the language provides a step towards integrating abstraction mechanisms and specification techniques. Some of the features in CDL* are compared to some of the features available in other languages, including distributed programming languages.>

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.

The objective of this work is to expand the study of generalized finite automata theory by introducing generalized finite state mappings (finite state mappings of trees). In the process, we hope to provide an algebraic framework in which to study formalizations of transformations (in the sense that linguists use the term) and translations of natural and artificial languages. The concepts, “syntax directed translation” [2,18,19, 22, 29] and “transformation” [11, 25] can be formulated quite neatly within this framework.

Let Nk denote the set of words over the alphabet Σk = {1, …, k}. Nk contains the null word which is denoted λ. We consider decision problems for various first-order interpreted predicate languages in which the variables range over Nk (k ≧ 2). Our main result is that there is no decision procedure for truth in the interpreted language which has the subword relation as its only non-logical primitive. This, together with known results summarized in Section 4, settles the decision problem for any language constructed on the basis of the relations and functions listed below.