Robin Milner and Automata theory

I always had the impression that the entire group of “process algebra” people didn’t know much about automata, but this is surprising.

But meanwhile I got somehow interested, and I don’t know how, in concurrency. I remember that, without linking it to verification particularly, I wondered about interacting automata. I had an idea that automata theory was inadequate, because it hadn’t said what it was for two automata to interact with each other. Except for the Krohn-Rhodes Representation Theorem, which said something about feeding the output of one automata into another. But there wasn’t interaction between the automata. (cite)

I don’t want to read too much into this, but Krohn-Rhodes theory  provides an algebraic result about efforts to simplify state machines by “dividing” them into simpler machines connected in a cascade (with information flowing one way). It has nothing to do with networks of communicating automata, a subject that was not particularly of interest during the early 1960s when the minimization of state machines was a focus for research. In fact, it is not unusual to find in papers of that period a definition of very general automata products in which the machines “interact”, followed by a definition of the special case of “loop free products” which were seen as critical in an age where reducing a design from 100 flip flops to 70 flip flops was a tough and important engineering task. The “network” case where there is arbitrary communication between machines was apparently seen as obvious.

I show an application of such a product in the recursion and state paper.