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…

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…