Milner’s Communication and Concurrency contrasts a notion of “bisimulation” with what he characterizes as the view in standard automata theory. Standard automata theory, however, has a much more interesting and well defined notion of both equivalence and concurrency than what
Judea Pearl’s mysterious claim
Pearl: Of course, but you cannot see this noble aspiration in scientific equations. The language of algebra is symmetric: If x tells us about y, then y tells us about x. I’m talking about deterministic relationships. There’s no way to write in mathematics a simple fact—for example,
Process algebra is based on a misunderstanding of automata theory
Robin Milner’s book Communication and Concurrency involves a take on state machines that is fundamentally incorrect. “Now in standard automata theory, an automaton is interpreted as a language i.e. as a set of strings over the alphabet.“ That’s not at
Practical State Machines for Computer Software and Engineering
Download paper. [gview file=”https://www.yodaiken.com/wp-content/uploads/2016/01/practical.pdf”]
Theories of abstract automata – Arbib
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 forms (of which the Turing machine is one) of substrate which
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 \( (H_1 \triangleleft H_2 … \triangleleft H_n=G)\) to state
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
Queues and algebra
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
simple lemma about pipelines
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
Process Algebra and classical automata
The long awaited process algebra paper is now finally available in PDF Reducing Process Algebra.