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,…

simple lemma about pipelines


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 (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…