§ Krohn Rhodes Theorem: Proof

• Recall writing an automata as semigroup and so on.
• A character is a permutation if its action on the state space is a permutation.
• A character is a reset if its action on the state space is a constant function.
• Permutation automata: all characters are permutations, so we can undo any sequence of characters.
• Reset automata: all characters are resets, but this is too boring! So all characters are resets, or identity. See that this acts like memory ! Since we can hold onto to information we had.
• The one bit memory automaton has 3 inputs, $0, 1, e$ where the state does what you'd expect: when $0$, state goes to $s_0$, when input is $1$, state goes to $s_1$, and $e$ keeps it the same state.
• We can write any auomata as a cascade of permutation and reset.
• So we can have things like $f(x, g(x, h(x)), h(x))$, where automata read inputs from before them.

§ Proof Sketch

• Step 1: Break down truncated run map of arbitrary automata with $n$ states into a cascade of a permutation reset automata (called $B$, for banned) and an $n-1$ state automaton $M'$.
• Step 2: recurse, till we get a 2-state automata. Now, all 2-state automata are permutation reset automata, so done!
• Step 3: Break apart the permutation reset automata into pure permutation + pure reset automata.
• Step 4: Break down the reset map for reset automata into a composition of the 1-bit-memory automata.
• Step 5: We can break down the permutation automata into finite simple groups if we want, but nah.

§ Step 1

• We start with an automata $M$ with $n$ states, and we want to write it as $B$, a permutation reset automata, and a new $(n-1)$ state automata $M'$.
• The automata $B$ keeps track of which state of $M$ we are not in at this moment in time!
• We set the initial state of $B$ to be a state that is different from the initial state of $M$.
• Now, for the alphabets, we want to make sure that $B$ moves to a state that $M$ does not move to!
• For any alphabet $a$, if the map $a_M : S(M) \to S(M)$ (the action of $a$ on $M$) does not have full image, then set $a_B$ to be that state that is not in the image! This is a reset map, and clearly maintains the banned invariant.
• Otherwise, the map $a_M$ must be a permutation (surjective = injective on endomorphism of finite set), and so we can set $b_M \equiv a_M$, since the transitoin map will map banned states to banned states.
• Great, we now need to design $M'$, which somehow uses the information of $B$ to do what $M$ used to to.
• The idea is to relabel the original states of $M$, minus the banned state $B$.
• $M'$ is an automata in the casecade, because it will have both the original alphabet $a_M$, as well as the output of $B$, where the output of $B$ is the current state of $B$.
• The input to $M'$ is going to be the input of $M$ and the output of $B$.
• So if we are in state $m' \in [0, n-1)$, and the output of $B$ is $b \in [0, n)$, and we get alphabet $a$, we create a new state m = m' >= b ? m' + 1 : m'.
• In some sense, since we build $B$ by "crossing out" a state in $M$, all we need to do in $M'$ is to relabel the states of $M$, by forgetting the state labaled by $B$. Using this, we can reconstruct the original automata $M$ with $B$ and $M'$.

§ Step 2: Recurse!

• Nothing much to be said.

§ Step 3: Break down Permutation-Reset into Permutation and Pure Reset

§ Permutation automata

• Take a permutation reset automata.
• a(0) = 1, a(1) = 2, and a(2) = 0. b(0) = b(1) = b(2) = 1. So this is a permutation reset automata.
• We will build two automata: first an automata $P$ that is pure permutations. The alphabet is the same, and its state space is the symmetric group of the original state space.
• In this case, the state space of $P$ is $S_3$. It's going to accumulate the permutations we have seen so far.
• For transition, if we see $a$, since it is a permutation, we compose $a_M$ to our current state. $\delta_P(f, a) = a_M \circ f$.
• For transition, If we see $b$, since it is not a permutation, we don't do anything. $\delta_P(f, b) = f$.

§ Reset automata

• If we do a reset before or after a permutation, it'll change what happens!
• The states of the reset automata is states of original automata
• Now, let's design the transtion map. Recall that this needs to be a reset automata.
• The invariant we will maintain is as follows: If we first change the state to the state of the reset automata, and we then apply the permutation map, we will reach the corresponding state in the original permutation-reset automata $M$.
• We start with the initial state of $M$.
• As input, it will receive both the original input, as well as the current state of the permutation automata (cascade)
• Key idea: if it receives $a$, since $a$ is a permutation, the permutation automata will compose the action of $a$, so we keep the (original) initial state.
• If it receives a $b$, $b$ is a reset, where we should reset to state 1. We want to change to a state such that when we run the permutation automata's $f$ on it, we will reach a $b$. So we set the transition map to $\delta(-, (b, f)) = f^{-1}(1)$
• Clearly, if we start at $f^{-1}(1)$, and we run $f$ on it, then we get to $1$!
• So the genius is to use the automata to keep track of "runs", where the resets destroy the state, and the permutations compose the state together.

§ Step 4: Break down Reset Automata into 1-bit Reset Automata

• Isn't this literally just building memory by writing stuff in binary?

§ References

• Proof adapted from "algebraic theory of automata" by Ginsburg
• Thomas Kern: Regular Languages and Model Theory 28: The Krohn-Rhodes Theorem