Cute semiautomoton diagram

Posted Thursday December 21 2023.

Wikipedia defines a semiautomon as

This is a deterministic automaton: when put in an initial state \(s_0\) and given a sequence of inputs \(i_0, i_1, i_2, \dots\), the resulting sequence of states is uniquely determined by the recurrence relation \(s_{t+1} = \mathsf{step}(s_t,i_t)\), where \(t=0,1,2,\cdots\).

A fair warning, everything I’m about to say is covered in depth on the Wikipedia page linked above. Alas…

Let \(\mathrm{Seq}(S)\) denote the set of all possible sequences of states, and likewise \(\mathrm{Seq}(I)\) the set of possible sequences of inputs.

Let \(Seq[S]\) and \(Seq[I]\) denote sequences of elements of \(S\) and \(I\), respectively. What we have described is a function \(\mathrm{run}: S \times Seq[I] \to Seq[S]\). The property that \(run\) satisfies is illustrated by the following commutative diagram:

In other words, starting in the top left corner with a initial state/input sequence pair \((s_0,(i_0,i_1,i_2,\dots)) \in S \times Seq[I]\), the following processes do the same thing

  1. first apply “run”, yielding the sequence \((s_0,s_1,s_2,\dots)\), and then take the tail of that sequence, which is \((s_1,s_2,s_3,\cdots)\).

  2. split the input sequence into its head/tail pair, leading to \((s_0,i_0,(i_1,i_2,i_3,\dots))\). Then apply \(f\) to \((s_0,i_0)\) in the first two positions to get \((s_1,(i_1,i_2,i_3,\dots))\). Finally apply run to get \((s_1,s_2,s_3,\cdots)\).

Easier interpretation?

We can view the update rule as an action of \(I\) on \(S\). This uniquely determines a monoid action of the free monoid on I, on S.