automata

Process algebra versus state machines part 1

January 20, 2016 | 0 Comments

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 [...]

Theories of abstract automata – Arbib

December 12, 2015 | 0 Comments

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 [...]

the terrible effect of Krohn-Rhodes

December 4, 2013 | 0 Comments

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 [...]

Process algebra reconsidered

May 7, 2010 | 0 Comments

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 [...]

Queues and algebra

February 28, 2010 | 0 Comments

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 [...]

simple lemma about pipelines

February 25, 2010 | 0 Comments

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 [...]

Process algebra (updated)

July 9, 2009 | 0 Comments

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 [...]

Recursion and state

July 2, 2009 | 0 Comments

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 [...]