The following question arises in connection with problems in automata theory related to the road problem. Let $f_1, f_2: [N] \to [N]$ be maps such that $f_1([N]) \cup f_2([N]) = [N]$, i.e. such that the transformation semigroup $S = \langle f_1, f_2 \rangle$ is transitive. Let $A$ be the $N \times N$ matrix with $A_{ij} = \mathbf{1}_{\{f_1(i) = j\}} + \mathbf{1}_{\{f_2(i) = j\}}$, and let $p$ be the period of $A$, i.e. the gcd of the set $\{ k - \ell: A^k > 0, A^{\ell} > 0, k, \ell \in \mathbb{N} \}$.

(That is, $A$ is the adjacency matrix of a strongly connected digraph $G$ with period $p$ and out-degree $2$ at every vertex. We label the edges with $\{ 1, 2 \}$ so that every state has each outgoing symbol on one of its edges, and we have $f_k(i) = j$ iff there is an edge from $i$ to $j$ labeled $k$. I have presented the setup more or less backwards, relative to the usual presentation, because I want to emphasize points that I don't often see.)

For a permutation $\sigma \in S_N$, let $\sigma S = \langle f_1 \circ \sigma, f_2 \circ \sigma \rangle$. One way of phrasing the periodic version (due to Béal-Perrin and Budzban-Feinsilver) of Trakhtman's road colouring theorem, for out-degree $2$, is that unless $f_1 \equiv f_2$, in which case $\sigma S = S$ for all $\sigma$, then among the semigroups $\{ \sigma S : \sigma \in S_N \}$ there exist $\sigma$ and $f \in \sigma S$ such that $|f([N]) = p|$. (This is the minimum possible value, given $p$.) When $p = 1$, this means that some $\sigma S$ contains the $N$ constant maps.

Suppose that we didn't know the road colouring theorem. What could we say about the family $\{ \sigma S : \sigma \in S_N \}$? I am basically interested in any response to this vague question.

The following question arises in connection with problems in automata theory related to the road problem. Let $f_1, f_2: [N] \to [N]$ be maps such that the transformation semigroup $S = \langle f_1, f_2 \rangle$ is transitive. Let $A$ be the $N \times N$ matrix with $A_{ij} = \mathbf{1}_{\{f_1(i) = j\}} + \mathbf{1}_{\{f_2(i) = j\}}$, and let $p$ be the period of $A$, i.e. the gcd of the set $\{ k - \ell: A^k > 0, A^{\ell} > 0, k, \ell \in \mathbb{N} \}$.

(That is, $A$ is the adjacency matrix of a strongly connected digraph $G$ with period $p$ and out-degree $2$ at every vertex. We label the edges with $\{ 1, 2 \}$ so that every state has each outgoing symbol on one of its edges, and we have $f_k(i) = j$ iff there is an edge from $i$ to $j$ labeled $k$. I have presented the setup more or less backwards, relative to the usual presentation, because I want to emphasize points that I don't often see.)

For a permutation $\sigma \in S_N$, let $\sigma S = \langle f_1 \circ \sigma, f_2 \circ \sigma \rangle$. One way of phrasing the periodic version (due to Béal-Perrin and Budzban-Feinsilver) of Trakhtman's road colouring theorem, for out-degree $2$, is that unless $f_1 \equiv f_2$, in which case $\sigma S = S$ for all $\sigma$, then among the semigroups $\{ \sigma S : \sigma \in S_N \}$ there exist $\sigma$ and $f \in \sigma S$ such that $|f([N]) = p|$. (This is the minimum possible value, given $p$.) When $p = 1$, this means that some $\sigma S$ contains the $N$ constant maps.

Suppose that we didn't know the road colouring theorem. What could we say about the family $\{ \sigma S : \sigma \in S_N \}$? I am basically interested in any response to this vague question.