Systems software technology and business
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, given a sequence of events [...]
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. This immediately brings in the [...]
The long awaited process algebra paper is now finally available in PDF
Reducing Process Algebra.
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 literature and also to a [...]
Here’s Edsger Dijkstra discussing the birth of the use of axiomatics in computer science – the start of “formal methods” research. What’s striking is the assumed choice between “axiomatic” and “mechanistic” as if there was no other way. In a later note he writes:
And now we are back at our old dilemma. Either we take [...]
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 state machine presentations in [...]