Standard Automata Theory and Process Algebra

Chapter 4, of "Communication and Concurrency"[11] starts with:

We begin … by showing the need for a notion of equality stronger than that found standard automata theory […] in standard automata theory an automaton is interpreted as a language."([11] p. 85).

Baeten[2] puts it this way

On automata, the basic notion of equivalence is language equivalence: a behaviour is characterized by the set of executions from the initial state to a final state.

A great deal of the automata theory literature, however, concerns differences between state machines that accept the same language. Rabin and Scott[9], in a 1959 paper discuss minimization via the Myhill congruence and also the distinction between deterministic and non-deterministic automata that accept the same language. Minimization involves reducing the state set of distinct state machines that "do the same thing" or recognize the same language. These machines are equivalent in one sense and not in another but are certainly not considered the same. Further, state machines are not confined to language acceptors (recognizers). Every digital circuit design text (e.g. [17]) discusses minimization of transducers, such as Mealy and Moore machines[8]. Acceptors are simply Moore type state machines with a binary output. Ginzburg’s 1968 text [4] explains ideas from the literature about state machine "coverings" and machine homomorphisms to characterize state machines, in general, ones with output, that have the same behavior but are structurally different. Hartmanis and Stearns work on factoring state machines [5, 6] and extensive work on Krohn-Rhodes [7], much of which pre-dates Milner’s work by a decade or more, are about distinguishing between state machines that do the same thing by their product structure or the algebraic structures of their underlying monoids [15, 1]. Hartmanis, in 1962, specifically discusses connecting concurrent Moore machines in a product form (see also Gecseg’s monograph [3] and my own use of concurrent products in [18]).

To illustrate his point about equivalence, Milner provides two state diagrams

and explains

if we take $A_{2}$ and $B_{2}$ to be the accepting states of our two automata, we can argue … that A and B denote the same language. …
But we now argue in favour of another interpretation in which A and B are different.

Milner used the same example in a previous book [10] where he asks "But are they equivalent in all senses?"

In "standard automata theory" A and B are definitely not equivalent in all senses. One is an NFA and the other is a DFA, after all. What Milner may have meant is that recognizers like A and B do not directly provide the semantics of Process Algebra "communicating processes".

According to our earlier treatment of examples, A and B are agents with may interact with their environment though the ports $a$, $b$, $c$, and $d$. We imagine an experimenter trying to interact with the agent A or with B through its ports; think of each port as a button which is unlocked if the agent can perform the associated action and can be depressed to make it do the action, otherwise the button is locked and cannot be depressed. "

… after the $a$-button is depressed [ in the initial state] a difference emerges between A and B. For A — which is deterministic — $b$ and $c$ will be unlocked, while for B — which is non-deterministic — sometimes only $c$ will be unlocked. — from Communication and Concurrency.

But, under this interpretation, A and B are not being employed as recognizers at all: they somehow have outputs which indicate what "buttons can be pressed" or accept additional inputs which model the event of an attempted button push. All of this is straightforward with a Moore machine - the kind of thing one learns in an introductory digital design class. On the other hand, if one assumes that state machines are limited to language acceptors which output only a binary accept/reject, and then treats these acceptors as if their internal state was also visible output, things won’t make much sense.

All of this is even more perplexing because in an 1971 paper[12], Milner references and uses the automata theoretic concepts of "covering" and "machine homorphism" explained in Ginzburg’s 1968 text on automata theory[4]. Park[14], who is generally credited with the concept of "bisimulation" in process algebra also references Ginzburg’s definition of covering.

Milner wrote in 1971[12]:

Condition (ii) simply states that R is a weak homomorphism between the algebraic structures (D,F (D’,F’). This concept is used in automata theory to define the notion of covering - see for example Ginzburg (7, p. 98.)

Here’s how Ginzburg explains it:

The meaning of [B covers A] is that to every state $s^{A}$ in $S^{A}$ there corresponds at least one state $s^{B}\in S^{B}$, such that when started in $s^{B}$, $B$ performs all the translations done by $A$. [..]
If for some A and B, B covers A and A covers B, these automata are said to be equivalent. (p 97) — [4].

According to this definition B does not cover A (there is no B state to map $A_{1}$ to) but A does cover B. So the state machines are still not equivalent.

Sangiorgi[16] has a much more detailed discussion of the automata theoretic origins of "bisimulation" from a process algebra point of view. What differences there are between covering and bisimulation is not something I address here, however, it is interesting that much of Ginzburg’s text is concerned with the direct and cascade product of concurrent state machines but that process algebra is very much based on the idea that automata cannot be connected into systems of communicating components within "standard automata theory". The cascade product connects factors in series and the text by Ginzburg references and draws from a 1962 paper by Hartmanis [5] called the "Loop-free structure of sequential machines" which specifically describes a more general automata product of Moore machines where there is arbitrary interaction between components as well as the loop-free products. Hartmanis writes:

We shall say this set of interconnected machines is concurrently operating if the next state […] of each machine $M_{i}$ depends on the present state of $M_{i}$, the present outputs (which depend only on the present states) of the machines to which it is connected, and the present external input. (page 117)

I show how to use the general product in [19] which treats state machines as maps from finite sequences to output values and uses a form of recursive composition to construct concurrent products.

And yet Baeten[2] in his 2005 "History of Process Algebra" writes

Basically, what is missing [in automata theory] is the notion of interaction: during the execution from initial state to final state, a system may interact with another system. This is needed in order to describe parallel or distributed systems, or so-called reactive systems.

which essentially dismisses not only the entire field of automata products but Moore and Mealy machines.

This summary is somewhat understandable because by the 1970s the computer science work on automata products had become marginal and automata theory in all respects was not at all well known, particularly within the formal methods and process algebra research communities. However, while many computer scientists worked on alternatives to automata theory, Moore machines continued to be widely employed by computer architects and electrical engineers in circuit design.