Search

Several concepts of algebras with solutions of recursive equation systems are compared: CPO-enrichable algebras are proved to be iteration algebras of Z. Esik, and iteration algebras are a special case of the recently introduced Elgot algebras (which are the monadic algebras for the free iterative monad). Another special case of iteration algebras are the iterative algebras of E. Nelson and J. Tiuryn, which are algebras with unique solutions of all guarded systems. For each of the above classes of algebras an example is provided showing that the inclusion in a wider class is proper.

The axioms of iteration 2-theories capture, up to isomorphism, the equational properties of iteration in conjunction with horizontal and vertical composition in all algebraically complete categories. We give a concrete representation of the free iteration 2-theory generated by a 2-signature.

Sabadini, Walters and others have developed a categorical, machine based theory of concurrency in which there are four essential aspects: a distributive category of data-types; a bicategory Mach whose objects are data types, and whose arrows are input-output machines built from data types; a semantic category (or categories) Sem, suitable to contain the behaviors of machines, and a functor, “behavior”: Mach→Sem. Suitable operations on machines and semantics are found so that the behavior functor preserves these operations. Then, if each machine is decomposable into primitive machines using these operations, the behavior of a general machine is deducible from the behavior of its parts. The theory of non-deterministic finite state automata provides an example of the paradigm and also throws some light on the classical theory of finite state automata. We describe a bicategory whose objects are natural numbers, in which an arrow M: n→p is a finite state automaton with n input states, p output states, and some additional internal states; we require that no transitions begin at output states or end at input states. A machine is represented by an q+n by q+p matrix. The bicategory supports additional operations: non-deterministic choice, parallel interleaving, and feedback. Enough operations are imposed on machines to show that each machine may be obtained from some atomic ones by means of the operations. The semantic category is the (Bloom-Esik) iteration theory Mat (X✶ whose objects are natural numbers and whose arrows from n to p are n×p matrices with entries in the semiring of languages. The behavior functor associates to a machine M: n→p a matrix |M| of languages, one language to each pair of input and output states. Behavior preserves composition, feedback, takes non-deterministic choice to union, and parallel-interleaving to shuffle. Thus, behavior gives a compositional semantics to a primitive notion of concurrent processes.

A result obtained in Ref. 2 for least prefixed points in order enriched cartesian closed categories is generalized to initiality in cartesian closed 2-categories. In brief, the result is that if a fixed point operation on a cartesian closed 2-category is defined by initiality, then under a mild condition, the operation satisfies the cartesian Conway identities and the abstraction identity. In addition, we show that the operation satisfies the power identities, and hence, except for the law a**=a*, the analogues of Conway’s classical identities for the regular sets.

We describe explicitly the free algebras in the equational class generated by all algebras of binary relations with operations of union, composition, converse and reflexive transitive closure and neutral elements 0 (empty relation) and 1 (identity relation). We show the corresponding equational theory is decidable by reducing the problem to a question about regular sets. Similar results are given for two related equational theories.

This paper extends Part 1 of the paper with the same title. Here, matricial iteration theories Matr(S; V) are characterized by identities involving theory operations, a star operation S → S and an omega operation S → V. The initial matricial iteration theory is described explicitly. One answer is given to the following question: If T0 is a submatricial theory of the matricial theory T which is an iteration theory, when can the star and omega operations on T0 be extended to T so that T becomes an iteration theory? Applications to program correctness logic and to finding equational axioms for the regular sets are indicated.

We consider partial Conway semirings and partial iteration semirings, both introduced by Bloom, Esik, Kuich [2]. We develop a theory of cycle-free elements in partial iterative semirings that allows us to define cycle-free finite automata in partial iterative semirings and to prove a Kleene Theorem. We apply these results to power series over a graded monoid with discounting.

We solve fixed point equations over finite and infinite words by initiality. By considering equations without and with parameters, two families of words arise, the regular and the algebraic words. Regular words were introduced by Courcelle in the late 1970's. We provide a summary of results on regular words, some of which have been obtained very recently, and include some new results for algebraic words.

The axioms of iteration 2-theories capture the equational properties of iteration in conjunction with horizontal and vertical composition in all algebraically complete categories. We give a concrete representation of the free iteration 2-theory generated by a 2-signature.

All known structures involving a constructively obtainable fixed point (or iteration) operation satisfy the equational laws defining iteration theories. Hence, there seems to be a general equational theory of iteration. This paper provides evidence that there is no general implicational theory of iteration. In particular, the quasi-variety generated by the continuous ordered theories, in which fixed point equations have least solutions, is incomparable with the quasi-variety generated by the pointed iterative theories, in which fixed point equations have unique solutions.

Recall the definition of matricial theories from Section 3.5.3. Since each matricial theory can be represented as a theory Matr(S; V) for some semiring module pair (S;V), we will be considering only matricial theories of this sort. A matricial iteration theory is a matricial theory which is simultaneously an iteration theory. We show that when T = Matr(S; V) is a matricial iteration theory, the dagger operation determines and is determined by a star operation on the semiring S and an omega operation ω: S → V from the semiring to the module.

We will review briefly some of the main concepts of standard universal algebra in order to motivate the definition of one of our central concepts: algebraic theories. We will show how theories are related to equational classes of algebras. Most of the facts mentioned in this chapter are well-known in some form.

An abstract logic 〈A, C〉 consists of a finitary algebraA and a closure systemC onA. C induces two other closure systems onA, CP andCI, by projective and inductive generation respectively. The various relations amongC, CP andCI are determined. The special case thatC is the standard equational closure system on monadic terms is studied in detail. The behavior of Boolean logics with respect to projective and inductive generation is determined.

The equational properties of iteration, when combined with composition and pairing, are captured by the notion of “iteration theory,” which was introduced in [SIAM J. Comput., 9 (1980), pp. 26–45; 9 (1980), pp. 525–540]. We believe, although all of our evidence will not be exhibited here, that every iterative construction satisfies at least the properties of iteration theories. In this paper, axiomatizations are given for several varieties of iteration theories which occur naturally in the semantics of programming languages, i.e., those generated by theories of trees [J. Comput. Sys. Sci., 16 (1978), pp. 362–399], theories of sequacious functions [Proc. 1973 Colloquium, Vol. 80, Studies in Logic, North Holland, Amsterdam, 1975; pp. 175–230], theories of partial functions, and theories of both sequacious and partial functions with distinguished predicates. We show which additional equations must be added to the axioms for iteration theories [Comput. Ling. Comput. Lang., 14 (1980), pp. 183–207] in order to ...

A signed ∑-equation is an expression of the form t ≈ t′ or t ≉t′, where t and t′ are ∑-terms (for some ranked set ∑). We characterize those classes of ∑-algebras which are models of a set of signed ∑-equations. Further we consider the problem of finding a complete deductive system analogous to equational logic for the logical consequence operation restricted to signed equations.

We describe a formalization of the equational logic of flowchart algorithms which has been shown to apply to a large class of other iterative processes connected with the theory of computation.