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 [...]
Please see this ever modifying page which seeks to demonstrate in a poorly organized, yet humorous manner, what the hell I’m trying to accomplish with this primitive recursive state machine stuff.
And as an added bonus – the great “Recursive Functions” book by Rozsa Peters contains the following remarkable note that has nothing to do with [...]
There’s a correspondence between the notions of “combinational” and “sequential” in digital circuit engineering and some structure in state machines (and therefore monoids) that seems interesting.
In digital logic, a “combinational” circuit like a logic gate has can be associated with a time T so that the output depends only on input signals applied over the [...]
The cross coupled latch is one of the greatest inventions of the 20th century
State machine models of timing and circuit design
Recursive transducers.
The long awaited process algebra paper is now finally available in PDF
Reducing Process Algebra.
11/23/2009 please see the updated version: here. Yet another version of the recursion/transducer paper . The main result is that simultaneous primitive recursion on strings corresponds to general products of state machines.
Primitive recursion on strings is analogous to primitive recursion on integers where we define f(0) = constant and f(n+1) = g(f(n)). In strings the [...]
An interesting paper appearing in ASPLOS proceedings provides a “deterministic” locking method
Kendo enforces a deterministic interleaving of lock acquisitions and specially declared non-protected reads through a novel dynamically load-balanced deterministic scheduling algorithm. The algorithm tracks the progress of each thread using performance counters to construct a deterministic logical time that is used to compute an [...]
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 [...]