### Process algebra versus state machines part 1

Robin Milner's influential book Communication and Concurrency involves a take on state machines that has always puzzled me. "Now in standard automata theory, an automaton is interpreted as a language," Milner writes "i.e. as a set of strings over the alphabet." That's not at all correct, but let's accept the…

### Theories of abstract automata – Arbib

We have said that automata theory deals with the realization of partial functions F: X* —» Y* by some finitely specifiable substrate. Before we specify in more detail the forms (of which the Turing machine is one) of substrate which have figured most prominently in automata theory, it is useful…

### the terrible effect of Krohn-Rhodes

One of the most interesting theorems in computer science is the Krohn-Rhodes theorem that shows a strong link between basic computer science and group theory. Crudely, the KR theorem extends Jordan-Holder \$latex (H_1 \triangleleft H_2 ... \triangleleft H_n=G)\$  to state machines, but it does it in a way that doesn't…

### Process algebra reconsidered

Paper is here. The following incorrect claim is not unusual in the process algebra literature. Basically, what is missing [in classical automata theory] is the notion of interaction: during the execution from initial state to fi nal state, a system may interact with another system. This is needed in order to…

### Queues and algebra

Suppose we have a state machine Q, that implements a common first in first out queue. The input alphabet of Q consists of "Deq" and "Enq x" where "x" ranges over a set of values, say, V. Let's fix the max length of Q at some constant k. As usual,…

The connection between group structure and pipeline design seems like it merits a lot more attention than it gets. It's not too hard to show that in a pipeline like the one to the right, the induced monoid of M1 must be a homomorphic image of the composite state machine.…

### Process Algebra and classical automata

The long awaited process algebra paper is now finally available in PDF Reducing Process Algebra.

### Process algebra (updated)

The first part of a critique of process algebra is below.Â  This relates to the Recursion and State paper and explicatory blog entry where I show how to compose classical automata and define them "abstractly" and to a complaint about the weak critique of automata theory in standard process algebra…

### Recursion and state

Despite some deep results, algebraic automata theory has fallen out of favor in theoretical computer science. Reasons include the disciplines failings such as a love of over-generality, weak mathematical background of people working on "formal methods", and gap between theoreticians and engineers. But perhaps the key reason is that traditional…