# Conjugacy for certain automorphisms of the one-sided shift via transducers

Collin Bleak and Feyishayo Olukoya

###### Abstract

We address the following open problem, implicit in the 1990 article
Automorphisms of one-sided subshifts of finite type of Boyle, Franks and
Kitchens (BFK):

> Does there exists an element $\psi$ in the group of automorphisms of the
> one-sided shift Aut($\\{0,1,\ldots,n-1\\}^{\mathbb{N}},\sigma_{n}$) so that
> all points of $\\{0,1,\ldots,n-1\\}^{\mathbb{N}}$ have orbits of length $n$
> under $\psi$ and $\psi$ is not conjugate to a permutation?

Here, by a _permutation_ we mean an automorphism of one-sided shift dynamical
system induced by a permutation of the symbol set $\\{0,1,\ldots,n-1\\}$.

We resolve this question by showing that any $\psi$ with properties as above
must be conjugate to a permutation.

Our techniques naturally extend those of BFK using the strongly synchronizing
automata technology developed here and in several articles of the authors and
collaborators (although, this article has been written to be largely self-
contained).

###### Contents

  1. 1 Introduction
  2. 2 Preliminaries
    1. 2.1 The natural numbers and some of its subsets
    2. 2.2 Words and infinite sequences
    3. 2.3 Automata and transducers
    4. 2.4 Increasing alphabet size and the dual automaton
    5. 2.5 Synchronizing automata and bisynchronizing transducers
    6. 2.6 De Bruijn graphs and folded automata
    7. 2.7 Automorphisms of digraphs underlying de Bruijn graphs and $\mathcal{H}_{n}$
    8. 2.8 Synchronizing sequences and collapse chains
  3. 3 Minimal actions of finite order elements of $\mathcal{H}_{n}$
    1. 3.1 Duals and Splits
    2. 3.2 Notational inconvenience.
    3. 3.3 Finite order elements of $\mathcal{H}_{n}$
      1. 3.3.1 Building $\mathscr{A}({A}^{\vee}_{k})$ from $A$
      2. 3.3.2 Duals, automata, and automorphisms
  4. 4 Water for the witch – shrinking conjugacy class representatives
    1. 4.1 Relabellings and automata sequences
      1. 4.1.1 Constructing discriminant permutations $\mathop{\mathrm{disc}}(s,t,Q)$
      2. 4.1.2 Discriminant permutations and amalgamation sequences
    2. 4.2 Relabellings along orbits
    3. 4.3 Shadow states
    4. 4.4 Relabelling through shadows
  5. 5 Conjugate to an $n$-cycle
    1. 5.1 An Example

##  1 Introduction

Let $n$ be a positive integer and set $X_{n}:=\\{0,1,\ldots,n-1\\}$. We will
use $X_{n}$ to represent our standard alphabet of size $n$ and we will denote
by $\sigma_{n}$ the usual shift map on $X_{n}^{\mathbb{N}}$. The group
$\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ of homeomorphisms of
$X_{n}^{\mathbb{N}}$ which commute with the shift map is called _the group of
automorphisms of the shift dynamical system_. This is a well-studied group in
symbolic dynamics, with the special property (first given by Hedlund in [10])
that if $\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ has
$(x_{0}x_{1}x_{2}\ldots)\phi=y_{0}y_{1}y_{2}\ldots$ then there is an integer
$k$ so that for all indices $i$, the value $y_{i}$ is determined by the finite
word $x_{i}x_{i+1}\ldots x_{i+k}$.

The paper [6] characterises all of the finite subgroups of the group
$\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$, shows that this group contains
non-abelian free groups whenever $n\geq 3$, and investigates other algebraic
structures of the group. The papers [7, 5] develop a conjugacy invariant for
the group $\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$, arising from the
action of the group on periodic words, which for an automorphism $\phi$ we
will denote as $\mathop{\mathrm{Sp}}(\phi)$ (this invariant consists of a
tuple: the well-known _gyration_ and _sign_ functions, together with _first
return_ data: bundled data associated to the permutation representation on
prime words of length $k$).

This article resolves the following open problem, implicit in [6], which Mike
Boyle suggested to us for its own sake, and, as a test of our approach.

Let $\Sigma_{n}$ represent the group of permutations of the set $X_{n}$. By a
mild abuse of language, we say
$\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ is a _permutation_ if
there is a fixed permutation $\alpha\in\Sigma_{n}$ so that if
$(x_{0}x_{1}x_{2}\ldots)\phi=y_{0}y_{1}y_{2}\ldots$ then we have
$y_{i}=(x_{i})\alpha$ for all $i$. We say a permutation is a _rotation_ if the
permutation from $\Sigma_{n}$ is an $n$-cycle. We can now state the problem:

> Does there exist an automorphism
> $\psi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ of order $n$ so that
> all points of $X_{n}^{\mathbb{N}}$ travel on orbits of size $n$, where
> $\psi$ is not conjugate to a rotation?

In [6] Boyle, Franks and Kitchens show that if $n$ is prime then any such
$\psi$ is in fact conjugate to a rotation. We show that the Boyle, Franks, and
Kitchens result holds for general $n$.

We have written this article so that it is essentially self-contained for
general researchers working with automorphisms of the shift. In particular, we
gather definitions and key constructions from [15] and [4] here to simplify
the presentation without insisting the reader peruse those articles to follow
our discussion. We use the highlighted technology to enhance the key method in
the article [6]. The paper [4] shows how to represent any automorphism $\phi$
of the one-sided shift by a particularly nice family of transducers (finite
state machines that transform inputs sequentially) while [15] investigates the
order problem for that same family of transducers. A key idea of [4] is that
any such transducer $T$ representing $\phi$ can be thought of as a triple
$(D,R,\phi_{*})$, where $D$ and $R$ are _strongly synchronizing automata_
(edge-labelled directed graphs with the particularly nice property of having a
_synchronizing sequence_) with $D$ representing the domain and $R$
representing the range, and where $\phi_{*}$ is an isomorphism of the
underlying digraphs $\Gamma(D)$ and $\Gamma(R)$ of $D$ and $R$ determined by
the action of $\phi$ on periodic words. In the case of a finite order element,
the domain and range automata can also be chosen to be identical.

In the article [6] the central method for studying finite subgroups of
$\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ is firstly to find an action of
the group on the underlying digraph of an automaton (now understood to be a
strongly synchronizing automaton). Once the first step is accomplished, the
group is decomposed as a composition series where each composition factor is
isomorphic to a subgroup of the symmetric group $\Sigma_{n}$ on $n$-points.
This is accomplished by pushing the action down along what is called an
“amalgamation sequence” (see Section 4.1.2 here) of the digraph until one has
an action by automorphisms on a particularly nice digraph. The construction
typically requires passing through the automorphism groups of various one-
sided shifts of finite type via topological conjugations induced by the
amalgamations.

Our first step simplifies this process. In particular we show that we can
always find an action of a finite subgroup of
$\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ on the underlying digraph of a
strongly synchronizing automaton whose amalgamation and synchronizing
sequences cohere (Section 4.1.2), thus we can push down along the
synchronizing sequence of that automaton without needing to possibly change
alphabet. This is already enough, when $n$ is prime, to show that every
element of order $p$ in $\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ is
conjugate in $\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ to a rotation.

However, to answer the open problem above, we need to go beyond this. Suppose
$\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ has order $n$ and with
the condition ($\star$) that all points of $X_{n}^{\mathbb{N}}$ travel on
orbits of size $n$. It turns out that ($\star$) is equivalent to the condition
that for any transducer $(A,A,\phi_{*})$ representing $\phi$, the action of
$\phi_{*}$ on $\Gamma(A)$ has the property that for every (based) circuit $C$
of $\Gamma(A)$ the orbit length of $C$ under this action is $n$. (We are using
based circuits here to avoid a circuit returning to itself with some non-
trivial rotation as counting as completing the orbit.) When $n$ is a prime
$p$, it is not hard to see that the action of $\phi_{*}$ on the underlying
digraph is limited in orbit lengths for edges and vertices to $1$ and $p$.
When $n$ is not prime, orbit lengths of edges and vertices can be any divisor
of $n$ even though all circuits have orbit length $n$. This last issue creates
problems when trying to implement the approach successfully carried out by
Boyle et al for $n$ prime.

We overcome this issue for such a $\phi$ with representative transducer
$(A,A,\phi_{*})$ with several technical lemmas. These aim to show that the
automaton $A$ can be “fluffed up” by adding shadow states (Section 4.3) to
create a new strongly synchronizing automaton $B$ with an induced and more
informative action $\psi_{*}$ on $\Gamma(B)$ so that $(B,B,\psi_{*})$ still
represents $\phi$. By ‘more informative’ we mean that the correct addition of
shadow states results in states and edges originally on orbits of length $<n$
having resulting orbits of length $n$. This new action makes it possible to
find a conjugate action of $\phi$ on a strongly synchronizing automaton of
strictly smaller size than $A$ (where the conjugacy occurs entirely with
$\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$).

Our approach can now be summarised as follows. First we conjugate to get a
(conjugate) action of $\phi$ on a strongly synchronizing automaton whose
synchronizing sequence coheres with the amalgamation sequence of its
underlying digraph. Then we have a series of “fluffing up” moves followed by
reductions via conjugation. Eventually, these processes result in a conjugate
action given by a transducer over a single state automaton with $n$ labelled
loops, where each edge is on an orbit of length $n$; our original element
$\phi$ must then be conjugate to a rotation.

The example in Section 5.1 might prove helpful to the reader as an
illustration of our approach and of the difficulties discussed above.

The property of being a strongly synchronizing automaton is equivalent to that
of being a _folded de Bruijn graph_. Crucial to the approach we have sketched
out is the process: given a finite order element
$\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$, find the minimal folded
de Bruijn graph $\Gamma$ so that $\phi$ acts faithfully on $\Gamma$ by
automorphisms. The following is essentially a result from [4] stated in our
context (see Lemma 3.4 and Theorem 3.5, below).

######  Theorem 1.1.

Let $n\geq 2$ be an integer and suppose
$\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ is a finite order
element. There is an effective process for determining $\Gamma_{\phi}$, the
minimal folded de Bruijn graph on an $n$ letter alphabet, so that $\phi$
induces a natural automorphism of $\Gamma_{\phi}$.

Finally, we can state the theorem which answers the question of Boyle.

######  Theorem 1.2.

Let $\phi\in\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$ be an element of
finite order. The following are equivalent:

  * •

$\phi$ is conjugate to a rotation;

  * •

every element of $X_{n}^{\mathbb{N}}$ is on an orbit of length $n$ under the
action of $A$; and

  * •

for any folded de Bruijn graph $\Gamma_{\phi}$ admitting a faithful action by
$\phi$ via an automorphism $\phi_{*}$, every (based) circuit of
$\Gamma_{\phi}$ is on an orbit of length $n$ under $\phi_{*}$.

It is unclear at the moment how much our approach depends on the condition
that “all circuits are on orbits of length $n$”. In work in progress we aim to
extend our current ideas towards resolving the conjugacy problem for finite
order elements of $\mbox{Aut}({X_{n}^{\mathbb{N}},\sigma_{n}})$.

### Acknowledgements

The authors are grateful for partial support from EPSRC research grant
EP/R032866/1. The second author is additionally grateful for support from
Leverhulme Trust Research Project Grant RPG-2017-159 and LMS ECF grant
ECF-1920-105. Finally, we are also grateful to Mike Boyle for conversations on
the question we address here.

##  2 Preliminaries

###  2.1 The natural numbers and some of its subsets

We use the notation $\mathbb{N}$ for the set $\\{0,1,2,\ldots\\}$; for
$j\in\mathbb{N}$ we write $\mathbb{N}_{j}$ for the set
$\\{i\in\mathbb{N}:1\geq j\\}$ of all natural numbers which are bigger than or
equal to $j$.

###  2.2 Words and infinite sequences

In this subsection we set up necessary notation for words and sequences.

Firstly, we employ all of the usual notation around finitary words over the
alphabet $X$. Namely, for a base set $X$, and natural $n$, $X^{n}$ is the set
of ordered $n$-tuples with coordinates from $X$. We call these the _words of
length $n$ (over alphabet $X$)_. By convention, we set
$X^{0}:=\\{\varepsilon\\}$ and we refer to $\varepsilon$ as _the empty word_
or _empty string_ , proclaiming this to be the same object, independent of the
(non-empty) set $X$ used as our alphabet. We set
$X^{*}:=\cup_{n\in\mathbb{N}}X^{n}$, the words of finite length over $X$ (this
is the Kleene-star operator). We also set
$X^{+}:=X^{*}\backslash\\{\varepsilon\\}$, the non-trivial/non-empty finite
length words over $X$. If $w\in X^{*}$ we set $|w|=n$ where $w\in X^{n}$, and
we call $|w|$ the _length of $w$_. If $X$ has a linear order $<$, then we give
$X^{*}$ the induced dictionary order. If $u\in X^{n}$ then we implicitly set
values $u_{i}\in X$ for $0\leq i<n$ so that $u=(u_{0},u_{i},\ldots,u_{n-1})$.
In this context, from here forward we will simply write $u=u_{0}u_{1}\ldots
u_{n-1}$. For $u\in X^{n}$ and $i\leq|u|$, we write $u_{[1,i]}$ for the prefix
$u_{1}\ldots u_{i}$ of $u$. Finally, if $u,v\in X^{*}$, so that
$u=u_{0}u_{1}\ldots u_{r-1}$ and $v=v_{0}v_{1}\ldots v_{s-1}$ then $uv$ will
represent the concatenation of these words: $uv:=u_{0}u_{1}\ldots
u_{r-1}v_{0}v_{1}\ldots v_{s-1}$, which is a word of length $r+s$ over $X$.

As in the paper [4], we take $X_{n}^{-\mathbb{N}}:=\\{\ldots
x_{-2}x_{-1}x_{0}\mid x_{i}\in X_{n}\\}$ as our shift space, with the shift
operator $\sigma_{n}$ defined by
$(x_{i})_{i\in-\mathbb{N}}\sigma_{n}=(y_{i})_{i\in-\mathbb{N}}$ where we have
$y_{i}=x_{i-1}$. We use the characterisation of elements of $\mathcal{H}_{n}$
as strongly synchronizing transducers corresponding to shift commuting
automorphisms of $X_{n}^{-\mathbb{N}}$. For a finite-length word over $X_{n}$
we may index this word with negative or positive indices as seems natural at
the time. When we are explicitly thinking of a finite subword $w\in X_{n}^{k}$
of a point $x\in X_{n}^{-\mathbb{N}}$ we will ordinarily index $w$ as
$w=w_{i-k+1}w_{i-k+2}\ldots w_{i}$ for some $i\in-\mathbb{N}$.

Suppose $k$ is a positive integer and $u=u_{-(k-1)}u_{-(k-2)}\ldots
u_{-1}u_{0}\in X_{n}^{k}$. Define $u^{\omega}\in X_{n}^{-\mathbb{N}}$, by
which notation we mean the point $\ldots x_{m}x_{m-1}\ldots x_{-1}x_{0}=:x$
where $x_{i}=u_{i\pmod{k}}$. The word $x\in X_{n}^{-\mathbb{N}}$ is called a
periodic word. The period of $x$ is the smallest $j\in\mathbb{N}$ such that
$(x)\sigma_{n}^{j}=x$. If the length $|u|$ is the period of the word $x$, then
$u$ is called prime. Alternatively $u$ is prime if there is no smaller word
$\gamma\in X_{n}^{+}$ such that $u=\gamma^{i}$ for some $i\geq 2$.

Write $\mathsf{X}_{n}^{k}$ for the full set of prime words of length $k$ over
the alphabet $X_{n}$.

Given two words $u,v\in X_{n}^{+}$ such that $|u|=|v|=r$, we call $v$ a
rotation of $u$ if there is an $i\in\mathbb{N}$ with
$(u^{\omega})\sigma_{n}^{i}=v^{\omega}$. In this case, we may refer to $v$ as
the _$i^{th}$ -rotation of $u$_ (even if $i>|u|)$.

It is a well-known fact that an element
$\phi\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ preserves the period of
a periodic element of $X_{n}^{-\mathbb{N}}$. In this way, the action of
$\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ on periodic words gives a
representation from $\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ to the
group $\Pi_{k\in\mathbb{N}}\mathop{\mathrm{Sym}}(\mathsf{X}_{n}^{k})$. For
$\phi\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$, write
$\overline{\phi}_{k}$ for the action of $\phi$ on prime words of length $k$
and write $\overline{\phi}$ for the element
$(\overline{\phi}_{k})_{k\in\mathbb{N}}\in\Pi_{k\in\mathbb{N}}\mathop{\mathrm{Sym}}(\mathsf{X}_{n}^{k})$.
The map $\overline{\phi}$ is the periodic point representation of
$\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$, introduced in [7].

###  2.3 Automata and transducers

An _automaton_ , in our context, is a triple $A=(X_{A},Q_{A},\pi_{A})$, where

  1. (a)

$X_{A}$ is a finite set called the _alphabet_ of $A$ (we assume that this has
cardinality $n$, and identify it with $X_{n}$, for some $n$);

  2. (b)

$Q_{A}$ is a finite set called the _set of states_ of $A$;

  3. (c)

$\pi_{A}$ is a function $X_{A}\times Q_{A}\to Q_{A}$, called the _transition
function_.

The _size_ of an automaton $A$ is the cardinality of its state set. We use the
notation $|A|$ for the size of the $A$.

We regard an automaton $A$ as operating as follows. If it is in state $q$ and
reads symbol $a$ (which we suppose to be written on an input tape), it moves
into state $\pi_{A}(a,q)$ before reading the next symbol. As this suggests, we
can imagine that the automaton $A$ is in the middle of an input word, reads
the next letter and moves to the right, possibly changing state in the
process.

We can extend the notation as follows. For $w\in X_{n}^{m}$, let
$\pi_{A}(w,q)$ be the final state of the automaton which reads the word $w$
from initial state $q$. Thus, if $w=x_{0}x_{1}\ldots x_{m-1}$, then

$\pi_{A}(w,q)=\pi_{A}(x_{m-1},\pi_{A}(x_{m-2},\ldots,\pi_{A}(x_{0},q)\ldots)).$

By convention, we take $\pi_{A}(\varepsilon,q)=q$.

For a given state $q\in Q_{A}$, we call the automaton $A$ which starts in
state $q$ an _initial automaton_ , denoted by $A_{q}$, and say that it is
_initialised_ at $q$.

An automaton $A$ can be represented by a labeled directed graph $G_{A}$, whose
vertex set $V_{A}$ is $Q_{A}$. For this directed graph there is a directed
edge labeled by $a\in X_{A}$ from $p$ to $q$ if $\pi_{A}(a,p)=q$. Representing
this, we determine the set $E_{A}$ of edges of $G_{A}$ to be the set of
triples

$E_{A}:=\\{(p,a,q)\mid\exists p,q\in Q_{A},a\in X_{A},\textrm{ so that
}\pi_{A}(a,p)=q\\}.$

In what follows, the labelled directed graph $G_{A}$ will be referred to as
the _underlying digraph for the automaton $A$_.

A _transducer_ is a quadruple $T=(X_{T},Q_{T},\pi_{T},\lambda_{T})$, where

  1. (a)

$(X_{T},Q_{T},\pi_{T})$ is an automaton;

  2. (b)

$\lambda_{T}:X_{T}\times Q_{T}\to X_{T}^{*}$ is the _output function_.

Formally such a transducer is an automaton which can write as well as read;
after reading symbol $a$ in state $q$, it writes the string $\lambda_{T}(a,q)$
on an output tape, and makes a transition into state $\pi_{T}(a,q)$. Thus, the
size of a transducer is the size of its underlying automaton. An _initial
transducer_ $T_{q}$ is simply a transducer which starts processing input from
state $q$. Transducers which are _synchronous_ (i.e., which always write one
letter whenever they read one letter) are also known as _Mealy machines_ (see
[9]), although we generally will not use that language here. Transducers which
are not synchronous are described as _asynchronous_ when this aspect of the
transducer is being highlighted. In this paper, we will only work with
synchronous transducers without an initial state, and, henceforth we simply
call these transducers.

In the same manner as for automata, we can extend the notation to allow
transducers to act on finite strings: we let $\pi_{T}(w,q)$ and
$\lambda_{T}(w,q)$ be, respectively, the final state and the concatenation of
all the outputs obtained when a transducer $T$ reads a string $w$ from a state
$q$.

A transducer $T$ can also be represented as an edge-labeled directed graph.
Again the vertex set is $Q_{T}$; now, if $\pi_{T}(a,q)=r$, we put an edge with
label $a|\lambda_{T}(a,q)$ from $q$ to $r$. In other words, the edge label
describes both the input and the output associated with that edge. We call $a$
the input label of the edge and $\lambda_{T}(a,q)$ the output label of the
edge.

For example, Figure 1 describes a synchronous transducer over the alphabet
$X_{2}$.

$a_{1}$$a_{2}$$0|0$$1|0$$1|1$$0|1$ Figure 1: A transducer over $X_{2}$

In what follows, we only use the language _automaton_ for those automata which
are not transducers. This allows us characterise a synchronous transducer $T$
as a pair of automata together with a directed graph isomorphism “gluing” the
two automata together as a domain automaton and a range automaton (we split
any edge label ‘$x|y$’ of $T$ as specifying the domain automaton edge with
label $x$ and the range automaton edge with label $y$).

We can regard any state $q$ of a transducer as acting on an infinite string
from $X_{n}^{\mathbb{N}}$ where $X_{n}$ is the alphabet. This action is given
by iterating the action on a single symbol; so the output string is given by

$\lambda_{T}(xw,q)=\lambda_{T}(x,q)\lambda_{T}(w,\pi_{T}(x,q)).$

Thus $T_{q}$ induces a map $w\mapsto\lambda_{T}(w,q)$ from
$X_{n}^{\mathbb{N}}$ to itself; it is easy to see that this map is continuous.
If it is a homeomorphism, then we call the state $q$ a _homeomorphism state_.
We write $\mbox{Im}{(q)}$ for the image of the map induced by $T_{q}$.

Two states $q_{1}$ and $q_{2}$ are said to be _$\omega$ -equivalent_ if the
transducers $T_{q_{1}}$ and $T_{q_{2}}$ induce the same continuous map. (This
can be checked in finite time, see [9].) More generally, we say that two
initial transducers $T_{q}$ and $T^{\prime}_{q^{\prime}}$ are _$\omega$
-equivalent_ if they induce the same continuous map on $X_{n}^{\mathbb{N}}$.

A transducer is said to be _minimal_ if no two states are $\omega$-equivalent.
For a transducer $T$, two states $q_{1}$ and $q_{2}$ are $\omega$-equivalent
if $\lambda_{T}(a,q_{1})=\lambda_{T}(a,q_{2})$ for any finite word $a\in
X_{n}^{*}$. Moreover, if $q_{1}$ and $q_{2}$ are $\omega$-equivalent states of
a synchronous transducer, then for any finite word $a\in X_{n}^{p}$,
$\pi_{T}(a,q_{1})$ and $\pi_{T}(a,q_{2})$ are also $\omega$-equivalent states.

Two minimal non-initial transducers $T$ and $U$ are said to be _$\omega$
-equal_ if there is a bijection $f:Q_{T}\to Q_{U}$, such that for any $q\in
Q_{T}$, $T_{q}$ is $\omega$-equivalent to $U_{(q)f}$. Two minimal initial
transducers $T_{p}$ and $U_{q}$ are said to be $\omega$-equal if they are
$\omega$-equal as non-initial transducers and there is a bijection $f:Q_{T}\to
Q_{U}$ witnessing this which satisfies the equality $(p)f=q$. We use the
symbol ‘$=$’ to represent $\omega$-equality of initial and non-initial
transducers. Two non-initial transducers $T$ and $U$ are said to be _$\omega$
-equivalent_ if they have $\omega$-equal minimal representatives, and in this
case we might instead say _$T$ and $U$ represent the same transformation_.

In the class of synchronous transducers, the $\omega$-equivalence class of any
transducer has a unique minimal representative.

Throughout this article, as a matter of convenience, we shall not distinguish
between $\omega$-equivalent transducers. Thus, for example, we introduce
various groups as if the elements of those groups are transducers, whereas the
elements of these groups are in fact $\omega$-equivalence classes of
transducers.

Given two transducers $T=(X_{n},Q_{T},\pi_{T},\lambda_{T})$ and
$U=(X_{n},Q_{U},\pi_{U},\lambda_{U})$ with the same alphabet $X_{n}$, we
define their product $T*U$. The intuition is that the output for $T$ will
become the input for $U$. Thus we take the alphabet of $T*U$ to be $X_{n}$,
the set of states to be $Q_{T*U}=Q_{T}\times Q_{U}$, and define the transition
and rewrite functions by the rules

$\displaystyle\pi_{T*U}(x,(p,q))$ $\displaystyle=$
$\displaystyle(\pi_{T}(x,p),\pi_{U}(\lambda_{T}(x,p),q)),$
$\displaystyle\lambda_{T*U}(x,(p,q))$ $\displaystyle=$
$\displaystyle\lambda_{U}(\lambda_{T}(x,p),q),$

for $x\in X_{n}$, $p\in Q_{T}$ and $q\in Q_{U}$. Here we use the earlier
convention about extending $\lambda$ and $\pi$ to the case when the transducer
reads a finite string. If $T$ and $U$ are initial with initial states $q$ and
$p$ respectively then the state $(q,p)$ is considered the initial state of the
product transducer $T*U$.

In automata theory a synchronous (not necessarily initial) transducer
$T=(X_{n},Q_{T},\pi_{T},\lambda_{T})$ is _invertible_ if for any state $q$ of
$T$, the map $\rho_{q}:=\lambda_{T}(\centerdot,q):X_{n}\to X_{n}$ is a
bijection. In this case the inverse of $T$ is the transducer $T^{-1}$ with
state set $Q_{T^{-1}}:=\\{q^{-1}\mid q\in Q_{T}\\}$, transition function
$\pi_{T^{-1}}:X_{n}\times Q_{T^{-1}}\to Q_{T^{-1}}$ defined by
$(x,p^{-1})\mapsto q^{-1}$ if and only if $\pi_{T}((x)\rho_{p}^{-1},p)=q$, and
output function $\lambda_{T^{-1}}:X_{n}\times Q_{T^{-1}}\to X_{n}$ defined by
$(x,p)\mapsto(x)\rho_{p}^{-1}$. Thus, in the graph of the transducer $T$ we
simply switch the input labels with the output labels and append ‘-1’ to the
state names.

We are concerned only with invertible, synchronous transducers in this
article.

###  2.4 Increasing alphabet size and the dual automaton

We require a couple of standard constructions in the theory of synchronous
automata in this work.

First we consider the ‘paths to letters’ construction. Let $T$ be a transducer
over the alphabet $X_{n}$. Let $m\in\mathbb{N}_{1}$. Write $T(m)$ for the
transducer over the alphabet $X_{n}^{m}$ with state set $Q_{T}$ and transition
and output functions $\pi_{T(m)}$, $\lambda_{T(m)}$ satisfying the following
conditions. For $x\in X_{n}^{m}$ and $q\in Q_{T}$ we set $\pi_{T(m)}(x,q)=p$
if and only if $\pi_{T}(x,q)=p$ in $T$; we set
$\lambda_{T(m)}(x,q):=\lambda_{T}(x,q)$. It is clear that if $T$ is minimal
and invertible, the $T(m)$ is also minimal and invertible.

The other construction we require is the _dual automaton_ (see [1, 14]).

Again let $T$ be a transducer over the alphabet $X_{n}$. Set
${T}^{\vee}=\langle Q_{T},X_{n},{\pi}^{\vee}_{T},{\lambda}^{\vee}_{T}\rangle$,
that is the state set of ${T}^{\vee}$ is the set $X_{n}$, the alphabet of
${T}^{\vee}$ is the state set $Q_{T}$ of $T$, and the transition
${\pi}^{\vee}_{T}$ and output functions ${\lambda}^{\vee}_{T}$ are defined as
follows. For $q\in Q_{T}$ and $x\in X_{n}$, ${\pi}^{\vee}_{{T}}(q,x)=y$ and
${\lambda}^{\vee}_{{T}}(q,x)=p$ if and only if $\pi_{T}(x,q)=p$ and
$\lambda_{T}(x,q)=y$.

There is a connection between the two constructions. The following is standard
in the theory of synchronous automata and provides a key insight in the
analysis of [1].

######  Lemma 2.1.

Let $T$ be a synchronous transducer over alphabet $X_{n}$. For positive
natural $m$, we have $({T}^{\vee})^{m}={T(m)}^{\vee}$.

Note that to lighten our notation below, we may use the notation
${T}^{\vee}_{m}$ for the transducer ${T(m)}^{\vee}$.

Also observe that ${T^{-1}}^{\vee}$ is obtained from ${T}^{\vee}$ by
‘reversing the arrows’. That is if, $x,y\in X_{n}$, $q,p\in Q_{T}$ are such
that ${\pi}^{\vee}_{T}(q,x)=y$ and ${\lambda}^{\vee}(q,x)=p$, then
${\pi}^{\vee}_{T^{-1}}(q^{-1},y)=x$ and ${\lambda}^{\vee}(q^{-1},y)=p^{-1}$.

###  2.5 Synchronizing automata and bisynchronizing transducers

Given a natural number $k$, we say that an automaton $A$ with alphabet $X_{n}$
is _synchronizing at level $k$_ if there is a map
$\mathfrak{s}_{k}:X_{n}^{k}\mapsto Q_{A}$ such that, for all $q$ and any word
$w\in X_{n}^{k}$, we have $\pi_{A}(w,q)=\mathfrak{s}_{k}(w)$. In other words,
$A$ is synchronizing at level $k$ if, after reading a word $w$ of length $k$
from a state $q$, the final state depends only on $w$ and not on $q$. (Again
we use the extension of $\pi_{A}$ to allow the reading of an input string
rather than a single symbol.) We call $\mathfrak{s}_{k}(w)$ the state of $A$
_forced_ by $w$; the map $\mathfrak{s}_{k}$ is called the _synchronizing map
at level $k$_. An automaton $A$ is called _strongly synchronizing_ if it is
synchronizing at level $k$ for some $k$.

We remark here that the notion of synchronization occurs in automata theory in
considerations around the _Černý conjecture_ , in a weaker sense. A word $w$
is said to be a _reset word_ for $A$ if $\pi_{A}(w,q)$ is independent of $q$;
an automaton is called _synchronizing_ if it has a reset word [16, 2]. Our
definition of “synchonizing at level $k$”/“strongly synchronizing” requires
every word of length $k$ to be a reset word for the automaton.

If the automaton $A$ is synchronizing at level $k$, we define the _core_ of
$A$ to be the maximal sub-automaton with set of states those states in the
image of the map $\mathfrak{s}$. It is an easy observation that, if $A$ is
synchronizing at level $k$, then its core is an automaton in its own right
using the same alphabet, and is also synchronizing at level $k$. We denote
this automaton by $\mathop{\mathrm{core}}\nolimits(A)$. We say that an
automaton or transducer is _core_ if it is equal to its core.

Clearly, if $A$ is synchronizing at level $k$, then it is synchronizing at
level $l$ for all $l\geq k$.

Let $T_{q}$ be an initial transducer which is invertible with inverse
$T_{q}^{-1}$. If $T_{q}$ is synchronizing at level $k$, and $T_{q}^{-1}$ is
synchronizing at level $l$, we say that $T_{q}$ is _bisynchronizing_ at level
$(k,l)$. If $T_{q}$ is invertible and is synchronizing at level $k$ but not
bisynchronizing, we say that it is _one-way synchronizing_ at level $k$.

For a non-initial invertible transducer $T$ we also say $T$ is bi-
synchronizing (at level $(k,l)$) if both $T$ and its inverse $T^{-1}$ are
synchronizing at levels $k$ and $l$ respectively.

Note that if $T$ is a strongly synchronizing transducer, then for any
$m\in\mathbb{N}$, $T(m)$ is also strongly synchronizing. Moreover, if $k$ the
minimal synchronizing level of $T$, then $T(m)$ is synchronizing at level $1$
for any $m\geq k$ and, more generally, is synchronizing at level
$\lceil\nicefrac{{k}}{{m}}\rceil$.

######  Notation 2.2.

Let $T$ be a transducer which is synchronizing at level $k$ and let $l\geq k$
be any natural number. Then for any word $w\in X_{n}^{l}$, we write $q_{w}$
for the state $\mathfrak{s}_{l}(w)$, where $\mathfrak{s}_{l}:X_{n}^{l}\to
Q_{T}$ is the synchronizing map at level $l$.

The following result was proved in Bleak et al. [3].

######  Proposition 2.3.

Let $T$, $U$ be transducers which (as automata) are synchronizing at levels
$j$, $k$ respectively, Then $T*U$ is synchronizing at level $j+k$.

Note that in the statement of Proposition 2.3, the lowest synchronizing level
of $T*U$ might actually be less than $j+k$.

Let $T$ be a transducer which (regarded as an automaton) is synchronizing at
level $k$, then the core of $T$ (similarly denoted
$\mathop{\mathrm{core}}\nolimits(T)$) induces a continuous map

$f_{T}:X_{n}^{-\mathbb{N}}\to X_{n}^{-\mathbb{N}}$

as follows. Let $x\in X_{n}^{-\mathbb{N}}$ and set $y\in X_{n}^{-\mathbb{N}}$
to be the sequence defined by

$y_{i}=\lambda_{T}(x_{i},q_{x_{i-k}x_{i-(k-1)}\ldots x_{i-1}}).$

Note that

$\pi_{T}(x_{i},q_{x_{i-k}x_{i-(k-1)}\ldots
x_{i-1}})=q_{x_{i-k}x_{i-(k-1)}\ldots x_{i-1}}.$

Set

$(x)f_{T}=y.$

Thus, from the point of view of the transition function of $T$ we in fact
begin processing $x$ at $-\infty$ and move towards $x_{0}$. (This is in
keeping with our interpretation of transducer as representing machines
applying sliding block codes, where here, we are thinking of
$\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ as consisting of the sliding
block code transformations that require past information only to determine
what to do with a digit.) Note, moreover, that the map $f_{T}$ is independent
of the (valid) synchronizing level chosen to define it. We have the following
result:

######  Proposition 2.4.

[4] Let $T$ be a minimal transducer which is synchronizing at level $k$ and
which is core. Then
$f_{T}\in\mathop{\mathrm{End}}\nolimits(X_{n}^{-\mathbb{N}},\sigma_{n})$.

The transducer in Figure 1 induces the shift map on $X_{n}^{-\mathbb{N}}$.

In [3], the authors show that the set $\widetilde{\mathcal{H}_{n}}$ of minimal
finite synchronizing invertible synchronous core transducers is a monoid; the
monoid operation consists of taking the product of transducers and reducing it
by removing non-core states and identifying $\omega$-equivalent states to
obtain a minimal and synchronous representative.

Let $\mathcal{H}_{n}$ be the subset of $\widetilde{\mathcal{H}_{n}}$
consisting of transducers which are bi-synchronizing. A chief result of [4] is
that $\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})\cong\mathcal{H}_{n}$.

###  2.6 De Bruijn graphs and folded automata

The _de Bruijn graph_ $G(n,m)$ can be defined as follows, for integers $m\geq
1$ and $n\geq 2$. The vertex set is $X_{n}^{m}$, where $X_{n}$ is the alphabet
$\\{0,\ldots,n-1\\}$ of cardinality $n$. There is a directed arc from
$a_{0}\ldots a_{m-1}$ to $a_{1}a_{2}\ldots a_{m}$, with label $a_{m}$.

Note that, in the literature, the directed edge is also from $a_{0}a_{1}\ldots
a_{m-1}$ to $a_{1}\ldots a_{m-1}a_{m}$ and the label on this edge is often
given as the $(m+1)$-tuple $a_{0}a_{1}\ldots a_{m-1}a_{m}$. However, the
labelling given above produces an isomorphic graph and is better suited for
our purposes.

Figure 2 shows the de Bruijn graph $G(3,2)$.

$00$$11$$22$$01$$10$$02$$20$$12$$21$$0$$1$$2$$1$$0$$2$$2$$1$$0$$1$$0$$2$$1$$0$$2$$0$$1$$2$$0$$2$$1$$2$$0$$1$$0$$2$$1$
Figure 2: The de Bruijn graph $G(3,2)$.

Observe that the de Bruijn graph $G(n,m)$ describes an automaton over the
alphabet $X_{n}$. Moreover, this automaton is synchronizing at level $m$: when
it reads the string $b_{0}b_{1}\ldots b_{m-1}$ from any initial state, it
moves into the state labeled ${b_{0}b_{1}\ldots b_{m-1}}$.

The de Bruijn graph is, in a sense we now describe, the universal automaton
over $X_{n}$ which is synchronizing at level $m$.

We define a _folding_ of an automaton $A$ over the alphabet $X_{n}$ to be an
equivalence relation $\equiv$ on the state set of $A$ with the property that,
if $a\equiv a^{\prime}$ and $\pi_{A}(x,a)=b$,
$\pi_{A}(x,a^{\prime})=b^{\prime}$, then $b\equiv b^{\prime}$. That is,
reading the same letter from equivalent states takes the automaton to
equivalent states. If $\equiv$ is a folding of $A$, then we can uniquely
define the _folded automaton_ $A/{\equiv}$: the state set is the set of
$\equiv$-classes of states of $A$; and, denoting the $\equiv$-class of $a$ by
$[a]$, we have $\pi_{A/{\equiv}}(x,[a])=[\pi_{A}(x,a)]$ (note that this is
well-defined).

######  Proposition 2.5.

[4] The following are equivalent for an automaton $A$ on the alphabet $X_{n}$:

  * •

$A$ is synchronizing at level $m$, and is core;

  * •

$A$ is the folded automaton from a folding of the de Bruijn graph $G(n,m)$.

We may think of a de Bruijn graph $G(n,m)$ as determining a finite category,
with objects the foldings of $G(n,m)$ and with arrows digraph morphisms which
commute with the transition maps of the given automata. It is immediate in
that point of view that all such arrows are surjective digraph morphisms (and
indeed, these are folding maps).

###  2.7 Automorphisms of digraphs underlying de Bruijn graphs and
$\mathcal{H}_{n}$

In this section we describe finite order elements of $\mathcal{H}_{n}$ as
automorphisms of folded de Bruijn graphs.

Let $A$ be a finite automaton on edge-alphabet $X_{n}$. Recall (Section 2.3)
that an automaton $A$ may be regarded as labeled directed graph with vertex
set $Q_{A}$, and edge set $E_{A}\subset Q_{A}\times X_{n}\ \times Q_{A}$. We
let $G_{A}$ denote the unlabeled directed graph corresponding to an automaton
$A$, but we retain the triple $(p,x,q)$ to denote the edge of $G_{A}$
underlying the edge $(p,x,q)$ of $A$.

Let $\phi$ be an automorphism of the directed graph $G_{A}$. Let $H(A,\phi)$
be a transducer with

  * •

state set $Q_{H(A,\phi)}:=Q_{A}$,

  * •

alphabet set $X_{n}$,

  * •

transition function $\pi_{H(A,\phi)}:=\pi_{A}$, and

  * •

output function $\lambda_{H(A,\phi)}:X_{n}\times Q_{H(A,\phi)}\to X_{n}$,

where $\lambda_{H(A,\phi)}(x,p)=y$ if and only if there are edges $(p,x,q)$
and $(r,y,s)$ of $G_{A}$ so that $(p,x,q)$ is taken to $(r,y,s)$ by $\phi$.

The transducer $H(A,\phi)$ can be thought of as the result of gluing the
automaton $A$ to a copy of itself along the map $\phi$. That is, if $p,q\in
Q_{A}$ and $(p,x,q)$ is an edge from $p$ to $q$ with label $x$ in $A$, and if
$y$ is the label of the edge $((p,x,q))\phi$ in $A$, then the vertex $p$ is
identified with the vertex $(p)\phi$, the vertex $q$ with the vertex
$(q)\phi$, the edge $(p,x,q)$ is identified with the edge $((p,x,q))\phi$ and
has input label $x$ and the output label $y$.

######  Remark 2.6.

We make a few observations:

  1. (a)

For each state $q\in Q_{H(A,\phi)}$, the map
$\lambda_{H(A,\phi)}(\centerdot,q):X_{n}\to X_{n}$ is a bijection. This
follows from the definition of $G_{A}$: for each $x\in X_{n}$ there is
precisely one edge of the form $((q)\phi,x,p)$ based at the vertex $(q)\phi$.
It follows that the transducer $H(A,\phi)$ is invertible.

  2. (b)

If $A$ is synchronizing at level $k$ (and so a folding of $G(n,k)$ by
Proposition • ‣ 2.5) then both $H(A,\phi)$ and $H(A,\phi)^{-1}$ are
synchronizing at level $k$ hence the minimal representative
$\overline{H(A,\phi)}$ of $H(A,\phi)$ is an element of $\mathcal{H}_{n}$.

  3. (c)

In fact, for a state $q\in Q_{A}$, if $W_{k,q}$ is the set of words of length
$k$, that force the state $q$, i.e.,

$W_{k,q}:=\\{a\in X_{n}^{k}:\pi_{H(A,\phi)}(a,q)=q\\},$

then $\\{\lambda_{H(A,\phi)}(a,p)\mid a\in Q_{k,q},p\in Q_{H(A,\phi)}\\}$ is
equal to $W_{k,(q)\phi}$.

  4. (d)

An element of $\mathcal{H}_{n}$ which can be represented by a transducer
$H(A,\phi)$ for some folded de Bruijn graph $A$ and digraph automorphism
$\phi$ of $G_{A}$ must have finite order.

If $A\in\mathcal{H}_{n}$ and $B$ is an automaton so that there is a digraph
automorphism $\phi:G_{B}\to G_{B}$ so that $A$ and $H(B,\phi)$ represent the
same transformation then we say _$A$ is induced from $(B,\phi)$_.

###  2.8 Synchronizing sequences and collapse chains

We require an algorithm given in [3] for detecting when an automaton is
strongly synchronizing. We state a version below.

Let $A=(X_{n},Q_{A},\pi_{A})$ be an automaton. Define an equivalence relation
$\sim_{A}$ on the states of $A$ by $p\sim_{A}q$ if and only if the maps
$\pi_{A}(\cdot,p):Q_{A}\to Q_{A}$ and $\pi_{A}(\cdot,q):Q_{A}\to Q_{A}$ are
equal. For a state $q\in Q_{A}$ let $\mathsf{q}$ represent the equivalence
class of $q$ under $\sim_{A}$. Further set
$\mathsf{Q}_{\mathsf{A}}:=\\{\mathsf{q}\mid q\in Q_{A}\\}$ and let
${\pi}_{\mathsf{A}}:\mathsf{Q}_{\mathsf{A}}\to\mathsf{Q}_{\mathsf{A}}$ be
defined by ${\pi}_{\mathsf{A}}(x,\mathsf{q})=\mathsf{p}$ where
$p=\pi_{A}(x,q)$. Observe that $\pi_{\mathsf{A}}$ is a well defined map.
Define a new automaton
$\mathsf{A}=(X_{n},\mathsf{Q}_{\mathsf{A}},\pi_{\mathsf{A}})$ noting that
$|\mathsf{Q}_{\mathsf{A}}|\leq|Q_{A}|$ and $|\mathsf{Q}_{\mathsf{A}}|=|Q_{A}|$
implies that $A$ is isomorphic to $\mathsf{A}$.

Given an automaton $A$, let $A_{0}:=A,A_{1},A_{2},\ldots$ be the sequence of
automata such that $A_{i}=\mathsf{A}_{i-1}$ for all $i\geq 1$. We call the
sequence $(A_{i})_{i\in\mathbb{N}}$ the _synchronizing sequence of $A$_. We
make a few observations.

By definition each term in the synchronizing sequence is a folding of the
automaton which precedes it, therefore there is a $j\in\mathbb{N}$ such that
all the $A_{i}$ for $i\geq j$ are isomorphic to one another. By a simple
induction argument, for each $i$, the states of $A_{i}$ corresponds to a
partition of $Q_{A}$. We identify the states of $A_{i}$ with this partition.
For two states $q,p\in Q_{A}$ that belong to a state $P$ of $A_{i}$,
$\pi_{A}(x,q)$ and $\pi_{A}(x,p)$ belong to the same state of $Q_{A_{i}}$ for
all $x\in X_{n}$. We will use the language ‘two states of $A$ are identified
at level $i$’ if the two named states belong to the same element of
$Q_{A_{i}}$.

If the automaton $A$ is strongly synchronizing and core, then an easy
induction argument shows that all the terms in its synchronizing sequence are
core and strongly synchronizing as well (since they are all foldings of $A$).
For example if $A=G(n,m)$, then the first $m$ terms of the synchronizing
sequence of $A$ are $(G(n,m),G(n,m-1),G(n,m-2),\ldots,G(n,1)$, after this all
the terms in the sequence are the single state automaton on $X_{n}$.

The result below is from [3].

######  Theorem 2.7.

Let $A$ be an automaton and $A_{0}:=A,A_{1},A_{2},\ldots$ be the sequence of
automata such that $A_{i}=\mathsf{A}_{i-1}$ for all $i>1$. Then

  1. (a)

a pair of states $p,q\in Q_{A}$, belong to the same element $t\in Q_{A_{i}}$
if and only if for all words $a\in X_{n}^{i}$, $\pi_{A}(a,p)=\pi_{A}(a,q)$,
and

  2. (b)

$A$ is strongly synchronizing if and only if there is a $j\in\mathbb{N}$ such
that $|Q_{A_{j}}|=1$. The minimal $j$ for which $|A_{j}|=1$ is the minimal
synchronizing level of $A$.

We also require the notion of a collapse chain from [4]. Let $A$ and $B$ be
strongly synchronizing automata. Let $A=A_{0},A_{1},\ldots,A_{k}=B$ be a
sequence such that $A_{i+1}$ is obtained from $A_{i}$ by identifying pairs of
states $p\sim_{A_{i}}q$. We note that as distinct from the synchronizing
sequence, we do not necessarily make all possible identifications. Such a
sequence is called a collapse chain if at each step, we make the maximal
number of collapses possible relative to the final automaton $B$. That is, for
$u,v\in Q_{A}$ belonging to the same state of $B$, in the minimal $A_{i}$ such
that $[u]\sim_{A_{i}}[v]$, we have $[u]=[v]$ in $A_{i+1}$. We note that this
condition means that a collapse chain is unique. Therefore, for $B$ a strongly
synchronizing automaton, we say that $B$ belongs to a collapse chain of $A$ if
there is a collapse chain $A=A_{0},A_{1},\ldots,A_{k}=B$. In this case, we
call the collapse chain $A=A_{0},A_{1},\ldots,A_{k}=B$, the the collapse chain
from $A$ to $B$. If $B$ is a single state automaton, the collapse chain from
$A$ to $B$ is precisely the strongly synchronizing sequence of $A$. Thus a
collapse chain can be thought of as a synchronizing sequence relative to its
end point.

The following facts are straightforward. Let $A$ be a strongly synchronizing
automaton, and $B$ be an automaton which is a folding of $A$, then there is a
collapse chain from $A$ to $B$. Therefore $B$ belongs to a collapse chain of
$A$ if and only if $B$ is a folding of $A$. In particular if $B$ belongs to a
collapse chain of $A$, then $B$ is synchronizing at the minimal synchronizing
level of $A$.

The following result about collapse chains is proved similarly to Theorem 2.7.

######  Theorem 2.8.

Let $A$ be an automaton and $B$ be a folding of $A$. Let
$A_{0}:=A,A_{1},A_{2},\ldots,A_{m}=B$ be the collapse chain from $A$ to $B$.
Then a pair of states $p,q\in Q_{A}$ belong to the same element $t\in
Q_{A_{i}}$ if and only if $p,q$ belong to the same state of $Q_{B}$ and for
all words $a\in X_{n}^{i}$, $\pi_{A}(a,p)=\pi_{A}(a,q)$.

##  3 Minimal actions of finite order elements of $\mathcal{H}_{n}$

For this section, we will work using facts related to dual transducers for
strongly synchronizing transducers.

It has been shown in [12, 1, 14] that the dual ${T}^{\vee}$ transducer for a
synchronous transducer $T$ contains much information about the order of $T$,
but implicit in those works also, much information about the conjugacy class
of $T$. In [15] the dual is considered for strongly synchronizing transducers,
where it is shown that for infinite order strongly synchronizing transducers
the powers of the dual grow in size asymptotically exponentially while for
finite order transducers the dual generates a finite semigroup with a zero. In
this section we bring in some of the methods and results of those works. See
[4, 15] for more details than we give below.

###  3.1 Duals and Splits

Recall our definition of the dual of a transducer from Subsection 2.4. We will
mostly be working in a power of the dual of a transducer $T$, below.

We introduce the following notation. Let $T$ be a strongly synchronizing
transducer, and $q\in Q_{T}$ be a state. Then we write $W_{q}$ for the set of
words $\gamma\in X_{n}^{+}$ such that the map $\pi_{T}(\gamma,\cdot):Q_{T}\to
Q_{T}$ has image $\\{q\\}$.

Let $A$ be an element of $\mathcal{H}_{n}$, with synchronizing level $k$. Then
for $r\geq k$, ${A}^{\vee}_{r}$ has a _split_
$((p_{1},\ldots,p_{l}),(q_{1}\ldots,q_{l}),\Gamma)$ if and only if the
following depiction (see Figure 3) of the transitions in ${A}^{\vee}_{r}$ at
the state $\Gamma$ is valid:

$\Gamma$$\Gamma_{1}$$\Lambda_{1}$$\Lambda_{2}$$\Gamma_{2}$$\Lambda_{l-1}$$\Gamma_{l-1}$$\Lambda_{l}$$\Gamma_{l}$$p_{1}|s_{1}$$q_{1}|s_{1}$$p_{2}|s_{2}$$q_{2}|s_{2}$$q_{l}|s_{l}$$p_{l}|s_{l}$$\ast|t_{1}$$\sharp|t_{2}$
Figure 3: A split; the symbols $\ast$ and $\sharp$ represent arbitrary
elements of $Q_{A}$.

More formally, we have the following.

######  Definition 3.1 (Splits).

Let $A$ be an element of $\mathcal{H}_{n}$, with synchronizing level $k$ and
let $r\geq k$. Suppose there are

  * •

$l\in\mathbb{N}_{1}$,

  * •

elements
$(p_{1},p_{2},\ldots,p_{l}),(q_{1},q_{2},\ldots,q_{l}),(s_{1},s_{2},\ldots,s_{l})\in
Q_{A}^{l}$,

  * •

a word $\Gamma\in X_{n}^{r}\cap W_{s_{1}}$, and

  * •

distinct states $t_{1},t_{2}\in Q_{A}$

such that when we define sequences $\Gamma_{1},\Gamma_{2},\ldots,\Gamma_{l}$
and $\Lambda_{1},\Lambda_{2},\ldots,\Lambda_{l}$ by

  * •

$\Gamma_{1}=\lambda_{A}(\Gamma,p_{1})$ and
$\Lambda_{1}=\lambda_{A}(\Gamma,q_{1})$, and

  * •

for $1<i\leq l$, $\Gamma_{i}=\lambda_{A}(\Gamma_{i-1},p_{i})$ and
$\Lambda_{i}=\lambda_{A}(\Lambda_{i-1},q_{i})$,

then $\Gamma_{i},\Lambda_{i}\in W_{s_{i+1}}$ for all $1\leq i\leq l-1$,
$\Gamma_{l}\in W_{t_{1}}$ and $\Lambda_{l}\in W_{t_{2}}$. In this case we say
that ${A}^{\vee}_{r}$ _splits_.

We also say that the $l$-tuples $(p_{1},\ldots,p_{l})$ and
$(q_{1},\ldots,q_{l})$ _split ${A}^{\vee}_{r}$ (at $\Gamma$)_. We call
$\\{p_{1},q_{1}\\}$ the _top of the split_ , $\\{t_{1},t_{2}\\}$ the _bottom
of the split_ , and the triple
$((p_{1},\ldots,p_{l}),(q_{1}\ldots,q_{l}),\Gamma)$ a _split of
${A}^{\vee}_{r}$ (of length $l$)_.

N.B.: if we took $r<k$ in the definition of a split above, then there is no
guarantee that some word $\Gamma$ of length $r$ would not even be
synchronizing, and also no guarantee of the existence of any synchronizing
word of length $r$, so the definition above breaks down.

The following concept appears implicitly in the proof of Lemma 3.8.

######  Definition 3.2.

Let $A$ be an element of $\mathcal{H}_{n}$, with synchronizing level $k$. Let
$r\geq k$ and $((p_{1},\ldots,p_{l}),(q_{1}\ldots,q_{l}),\Gamma)$ be a split
of ${A}^{\vee}_{r}$. Let $\\{t_{1},t_{2}\\}$ be the bottom of this split. Then
we say that _the bottom of the split
$((p_{1},\ldots,p_{l}),(q_{1}\ldots,q_{l}),\Gamma)$ depends only on the top_
if the following conditions hold for any other tuples $U_{1},U_{2}\in
Q_{A}^{l-1}$:

  * •

the triple $((p_{1},U_{1}),(q_{1},U_{2}),\Gamma)$ is also a split with bottom
$\\{t_{1},t_{2}\\}$ and,

  * •

if $\lambda_{A^{l}}(\Gamma,(p_{1},\ldots,p_{l}))\in W_{t_{1}}$ and
$\lambda_{A^{l}}(\Gamma,(q_{1},\ldots,q_{l}))\in W_{t_{2}}$ then
$\lambda_{A^{l}}(\Gamma,(p_{1},U_{1}))\in W_{t_{1}}$ and
$\lambda_{A^{l}}(\Gamma,(q_{1},U_{2}))\in W_{t_{2}}$, and vice-versa.

Observe that if, for $r\geq k$, ${A}^{\vee}_{r}$ has a split
$((p_{1},\ldots,p_{l}),(q_{1}\ldots,q_{l}),\Gamma)$ whose bottom depends only
on the top, then $p_{1}\neq q_{1}$.

Splitting length as defined below is used explicitly in Lemma 3.8.

######  Definition 3.3.

For a transducer $A$, we define the $r$-splitting length of $A$ (for $r$
greater than or equal to the minimal synchronizing length) to be minimal $l$
such that there is a split of ${A}^{\vee}_{r}$ of length $l$. If there is no
such split then we set the $r$-splitting length of $A$ to be $\infty$.

Note that if, for $r\geq k$, ${A}^{\vee}_{r}$ has $r$-splitting length
$l<\infty$, then any split of length $l$ has the property that the bottom
depends only on the top as otherwise one can find a shorter split (see [15]).

###  3.2 Notational inconvenience.

We are soon to run into some collisions of notation.

Firstly, if $\phi\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$, then we can
represent $\phi$ by a (minimal) transducer $A_{\phi}\in\mathcal{H}_{n}$.

Secondly, if $A\in\mathcal{H}_{n}$, then $A$ represents an element
$\phi_{A}\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$.

Finally, if $\phi\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ has finite
order, then as we will see from Theorem 3.5 there is an automaton
$\mathscr{A}({A}^{\vee}_{k})$ and an automorphism $\psi$ of the underlying
digraph $G_{\mathscr{A}({A}^{\vee}_{k})}$ so that $A_{\phi}$ and
$H(\mathscr{A}({A}^{\vee}_{k}),\psi)$ represent the same element. It happens
that there is a way to define $\psi$ from $\phi$, and also, from $A_{\phi}$.
Similarly, we could have begun this paragraph with an element
$A\in\mathcal{H}_{n}$, in which case $\psi$ would be defined from both
$\phi_{A}$ and from $A$.

In order to unify our notation here, we will simply denote $\psi$ in the above
situation as $\phi_{A}$. This of course means that $\phi_{A}$ will represent
two different things (an automorphism of the one-sided shift, or
alternatively, an automorphism of a digraph underlying a folded de Bruijn
graph). We hope that confounding the notation in this way will not cause
confusion as it should be clear what is meant from context, noting as well
that the digraph homomorphism $\phi_{A}$ is the induced digraph homomorphism
that arises on $G_{\mathscr{A}({A}^{\vee}_{k})}$ by considering how $\phi$
maps infinite paths on $\mathscr{A}({A}^{\vee}_{k})$ to other infinite paths
on $\mathscr{A}({A}^{\vee}_{k})$.

###  3.3 Finite order elements of $\mathcal{H}_{n}$

In this subsection we build, for a finite order element $A\in\mathcal{H}_{n}$
and corresponding $\phi_{A}\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$,
the minimal strongly synchronizing automaton $\mathscr{A}({A}^{\vee}_{k})$
which $\phi_{A}$ can act on as an automorphism of the underlying directed
graph with $A$ being the minimal representative of
$H(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$.

Note that we will retain the notation $\phi_{A}$ for both the element of
$\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ corresponding to $A$ as well as
the digraph automorphism $\phi_{A}$ that is induced by this automorphism of
the shift.

Note that the process of determining $A_{\phi}\in\mathcal{H}_{n}$ from a given
element $\phi\in\mbox{Aut}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ is not
difficult: one simply relates states to different maps as determined by the
fixed viewing window (it is common for differing viewing-window strings to
correspond to the same map, the set of all such strings corresponding to
“same” map can be used effectively as the name of that state) and then one
records the local letter transformations as the edge labels. For details, see
[4].

####  3.3.1 Building $\mathscr{A}({A}^{\vee}_{k})$ from $A$

Let $A\in\mathcal{H}_{n}$ be of finite order.

In this subsubsection, we learn a process for building a strongly
synchronizing automaton $\mathscr{A}({A}^{\vee}_{k})$ so that $\phi_{A}$ acts
on the underlying digraph of $\mathscr{A}({A}^{\vee}_{k})$ by automorphisms in
such a way that $H(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$ has $A$ as its
minimal representative transducer. This process is essential in the proof that
follows for finding simplified elements in the conjugacy class representing
our given finite order element $A$. We will also given an example of the
process for a specific element.

In [15, Proposition 4.15] it is shown that there is $k\in\mathbb{N}$ such that
${A}^{\vee}_{k}$ is the zero of the semigroup generated by ${A}^{\vee}$. Fix
the minimal such $k\in\mathbb{N}$ so that ${A}^{\vee}_{k}$ is the zero of the
semigroup generated by ${A}^{\vee}$, and let $\overline{{A}^{\vee}_{k}}$ be
the minimal representative of ${A}^{\vee}_{k}$.

The following is a very useful fact from [15]: for every state $[\gamma]$ of
the zero $\overline{{A}^{\vee}_{k}}$, there is a word $W([\gamma])\in
Q_{A}^{+}$ such that for any input word $s\in Q_{A}^{+}$, the output when $s$
is processed from the state $[\gamma]$ of $\overline{{A}^{\vee}_{k}}$ is the
word $(W([\gamma]))^{l}W([\gamma])_{[1,m]}$, where, $|s|=l|W([\gamma])|+m$ and
$W([\gamma])_{[1,m]}$ is the length $m$ prefix of $(W([\gamma]))$. It follows
from this that $\overline{{A}^{\vee}_{k}}$ has the following structure: for
each state $[\gamma]$ (for $\gamma\in X_{n}^{k}$) there is $q_{[\gamma]}\in
Q_{A}$ so that for all $p\in Q_{A}$ we have

  * •

$\pi_{\overline{{A}^{\vee}_{k}}}(p,[\gamma])=[\gamma]\cdot A$, and

  * •

$\lambda_{\overline{{A}^{\vee}_{k}}}(p,[\gamma])=q_{[\gamma]}$.

We will call this the _$|Q_{A}|$ -parallel cycle structure of
$\overline{{A}^{\vee}_{k}}$_, or less formally, the _cyclical structure of
$\overline{{A}^{\vee}_{k}}$._

Form the automaton $\mathscr{A}({A}^{\vee}_{k})$ as follows. The states of
$\mathscr{A}({A}^{\vee}_{k})$ are the states $[\gamma]$ of
$\overline{{A}^{\vee}_{k}}$ and the transitions are given by the rule that for
$x\in X_{n}$, and $[\gamma]$ a state of $\overline{{A}^{\vee}_{k}}$, we set
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(x,[\gamma])=[\gamma_{[2,|\gamma|]}x]$. (For
this construction it does not matter which $\gamma\in X_{n}^{k}$ one picks
from the class $[\gamma]$, even though we use $\gamma$ explicitly in the
formula of the transition function: this follows since states of
$\overline{{A}^{\vee}_{k}}$ are $\omega$-equivalent classes of
${A}^{\vee}_{k}$.)

The following lemma is immediate from the definitions:

######  Lemma 3.4.

If $A\in\mathcal{H}_{n}$ be of finite order and let $k\in\mathbb{N}$ so that
${A}^{\vee}_{k}$ is the zero of the semigroup generated by ${A}^{\vee}$ then
the automaton $\mathscr{A}({A}^{\vee}_{k})$ is strongly synchronizing at level
$k$.

We also have the following translation (into our context) of the statement of
Theorem 4.5 of [4], where $A(G)$ in that theorem corresponds to
$\mathscr{A}({A}^{\vee}_{k})$ here, and where the group $G$ there is the group
$\langle A\rangle$ here.

######  Theorem 3.5.

Let $A\in\mathcal{H}_{n}$ be of finite order and let $k\in\mathbb{N}$ so that
${A}^{\vee}_{k}$ is the zero of the semigroup generated by ${A}^{\vee}$.

  1. (a)

$A$ acts as an automorphism $\phi_{A}$ of the digraph underlying
$\mathscr{A}({A}^{\vee}_{k})$ by mapping an edge
$([\gamma],x,[\gamma_{[2,|\gamma|]}x])$ to the edge
$(([\gamma])A,\lambda_{A}(x,q_{\gamma}),([\gamma_{[2,|\gamma|]}x])A)$ where
$([\gamma])A=[\lambda_{A}(\gamma,q)]$ for some $q\in Q_{A}$,

  2. (b)

The minimal representative of the transducer
$H(\mathscr{A}({A}^{\vee}_{k}),\phi_{A}^{i})$ is the transducer $A^{i}$.

######  Example 3.6.

Consider the transducer $A$ below.

$a_{0}$$a_{1}$$a_{2}$$a_{3}$$1|4$
$0|5$$2|0$$3|1$$4|2$$5|3$$4|2$$5|3$$0|4$$1|5$$2|1$$3|0$$1|4$$0|5$$4|2$
$5|3$$2|1$$3|0$$1|5$$0|4$$2|0$ $3|1$$4|2$$5|3$ Figure 4: An element
$A\in\mathcal{H}_{6}$ of order $6$.

The transducer $A$ of Figure 4 is bi-synchronizing at the second level. The
level 2 dual has 36 nodes and so we shall not give this below. However
utilising the AutomGrp package [13] in GAP [8], together with (in AutomGrp)
the function “MinimizationOfAutomaton( )” which returns an $\omega$-equivalent
automaton, applied to the second power of the dual automaton, we get the
result $\overline{{A}^{\vee}_{2}}$, depicted in Figure 5 (which is the zero of
the semigroup generated by the dual):

$q_{0}$$q_{1}$$q_{2}$$\ast|a_{1}$$\ast|a_{3}$$\ast|a_{2}$$p_{0}$$p_{1}$$p_{2}$$\ast|a_{0}$$\ast|a_{3}$$\ast|a_{2}$
Figure 5: The level 2 dual of $A$.

Considering the states $\\{q_{0},q_{1},q_{2},p_{0},p_{1},p_{2}\\}$ of
$\overline{{A}^{\vee}_{2}}$ as a partition of the words of length 2 over the
alphabet $\\{0,1,2,3,4,5\\}$, it is easy to see that

$\displaystyle q_{0}$ $\displaystyle=\\{00,01,10,11,40,41,50,51\\}\qquad\quad
p_{0}=\\{20,21,30,31\\}$ $\displaystyle q_{1}$
$\displaystyle=\\{24,25,34,35,44,45,54,55\\}\qquad\quad
p_{1}=\\{04,05,15,15\\}$ $\displaystyle q_{2}$
$\displaystyle=\\{02,03,12,13,22,23,32,33\\}\qquad\quad
p_{2}=\\{42,43,52,53\\}$

by verifying the 36 transitions from $q_{0}$ in $A$ using these input words,
and cross-checking state-change results against the transitions of
$\overline{{A}^{\vee}_{2}}$. From this we can calculate the transitions of
$\mathscr{A}({A}^{\vee}_{2})$, with the resulting automaton depicted in 6.

$p_{0}$$q_{0}$$q_{2}$$q_{1}$$p_{1}$$p_{2}$$1$
$0$$2$$3$$4$$5$$4$$5$$0$$1$$2$$3$$1$$0$$4$
$5$$2$$3$$1$$0$$2$$3$$4$$5$$2$$3$$5$$4$$1$$0$$0$$1$$3$$2$$4$$5$ Figure 6: The
automaton $\mathscr{A}({A}^{\vee}_{2})$

Notice that both the domain and range automaton of $A$ are foldings of
$\mathscr{A}({A}^{\vee}_{2})$. This phenomenon generalises, that is, for a
strongly synchronizing transducer $A$ representing an element of
$\mathcal{H}_{n}$ of finite order, both the domain and range automata of $A$
are foldings of $\mathscr{A}({A}^{\vee}_{k})$ (where $k$ is appropriately
chosen).

We revisit this example in Section 5.1 where we show that $A$ is conjugate to
a $6$-cycle. $\bigcirc$

####  3.3.2 Duals, automata, and automorphisms

In this subsubsection, we will prove that for finite order
$A\in\mathcal{H}_{n}$ and minimal $k$ so that ${A}^{\vee}_{k}$ is the zero of
the semigroup generated by ${A}^{\vee}$, that $\mathscr{A}({A}^{\vee}_{k})$ as
defined above is the minimal (strongly synchronizing) automaton so that $A$
can act on $\mathscr{A}({A}^{\vee}_{k})$ as an automorphism $\phi_{A}$, with
$(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$ inducing $A$.

We first require lemmata exploring the relationship between properties of
$\mathscr{A}({A}^{\vee}_{k})$ and of ${A}^{\vee}_{k}$.

Our first step is the following useful lemma about the automaton
$\mathscr{A}({A}^{\vee}_{k})$ constructed as above from a finite order element
$A\in\mathcal{H}_{n}$. In essence, it says that if two states $[\delta]$ and
$[\gamma]$ are distinct in $\mathscr{A}({A}^{\vee}_{k})$ but their two
transition functions are the same, then by following the cycles of the level
$k$ dual (by iteratively acting by $A$), we will eventually get to a pair of
states which have different output letters in the level $k$ dual, and at that
pair of locations, the states of $\mathscr{A}({A}^{\vee}_{k})$ will still
transition the same way, but the output functions of
$H(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$ at these states will disagree at the
first letter.

######  Lemma 3.7.

Let $A\in\mathcal{H}_{n}$ be finite order. Let $\gamma,\delta\in X_{n}^{k}$ be
such that the states $[\gamma],[\delta]$ of $\mathscr{A}({A}^{\vee}_{k})$ are
distinct. Suppose moreover that the maps
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\gamma])$ and
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\delta])$ coincide. Then there is a
natural $i$ with $0\leq i<o(A)$ and $x,y,y^{\prime}\in X_{n}$ such that $y\neq
y^{\prime}$,
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\gamma]A^{i})=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\delta]A^{i})$
but $A$ maps the edges

$([\gamma]A^{i},x,\pi_{\mathscr{A}({A}^{\vee}_{k})}(x,[\gamma]A^{i}))\textrm{
and }([\delta]A^{i},x,\pi_{\mathscr{A}({A}^{\vee}_{k})}(x,[\delta]A^{i}))$

respectively to the edges

$([\gamma]A^{i+1},y,\pi_{\mathscr{A}({A}^{\vee}_{k})}(y,[\gamma]A^{i+1}))\textrm{
and
}([\delta]A^{i+1},y^{\prime},\pi_{\mathscr{A}({A}^{\vee}_{k})}(y^{\prime},[\delta]A^{i+1})).$

###### Proof.

Let $w=W([\gamma])$ and $v=W([\delta])$. Since $[\gamma]\neq[\delta]$, we may
find words $u,w_{2},v_{2}\in Q_{A}^{\ast}$ and letters $t\neq t^{\prime}\in
Q_{A}$ such that $w=utw_{2}$ and $v=ut^{\prime}v_{2}$. Set $i-1:=|u|$. We note
that for any $j\in\mathbb{N}$ with $j\leq i-1$, a straightforward induction
argument shows, the edges
$([\gamma],a,\pi_{\mathscr{A}({A}^{\vee}_{k})}(a,[\gamma])A)$ and
$([\delta],a,\pi_{\mathscr{A}({A}^{\vee}_{k})}(q,[\delta]))$ map respectively
under $A^{j}$ to edges
$([\gamma]A^{j},b,\pi_{\mathscr{A}({A}^{\vee}_{k})}(a,[\gamma])A^{j})$ and
$([\delta]A^{j},b,\pi_{\mathscr{A}({A}^{\vee}_{k})}(q,[\delta])A^{j})$, where
$b$ = $\lambda_{A^{j}}(a,u_{[1,j]})$ (if $j=0$, take $b=a$). In particular it
follows that $\pi_{A}(\cdot,t)=\pi_{A}(\cdot,t^{\prime})$ and so, since $t\neq
t^{\prime}$, there is an $a\in X_{n}$ be such that
$y:=\lambda_{A}(a,t)\neq\lambda_{A}(a,t^{\prime})=y^{\prime}$. Let $x\in
X_{n}$ be such that $\lambda_{A^{i-1}}(x,u)=a$. Then it follows that the edges

$([\gamma]A^{i},x,\pi_{\mathscr{A}({A}^{\vee}_{k})}(x,[\gamma]A^{i}))\mbox{
and }([\delta]A^{i},x,\pi_{\mathscr{A}({A}^{\vee}_{k})}(x,[\delta]A^{i}))$

are mapped respectively under $A$, to the edges

$([\gamma]A^{i+1},y,\pi_{\mathscr{A}({A}^{\vee}_{k})}(y,[\gamma]A^{i+1}))\mbox{
and
}([\delta]A^{i+1},y^{\prime},\pi_{\mathscr{A}({A}^{\vee}_{k})}(y^{\prime},[\delta]A^{i+1})).$

$\Box$

Recall from Subsection 2.7 that if $A\in\mathcal{H}_{n}$ and $B$ is an
automaton so that there is a digraph automorphism $\phi:G_{B}\to G_{B}$ so
that $A$ and $H(B,\phi)$ represent the same transformation then we say _$A$ is
induced from $(B,\phi)$_.

Let $A\in\mathcal{H}_{n}$. We say a strongly synchronizing automaton _$B$ is
an automaton supporting $A$_ if there is a digraph automorphism $\phi$ of the
digraph $G_{B}$, with $A$ induced from $(B,\phi)$. In this situation, if there
is no proper folding $B^{\prime}$ of $B$ and digraph automorphism
$\phi^{\prime}:G_{B^{\prime}}\to G_{B^{\prime}}$ so that $A$ is induced from
$(B^{\prime},\phi^{\prime})$, then we say _$B$ is a minimal automaton
supporting $A$_ (or simply, that $B$ is minimal).

In the next lemma, we show that there is precisely one minimal automaton (up
to isomorphism of automata) supporting a finite order element $A$ of
$\mathcal{H}_{n}.$

######  Lemma 3.8.

Let $A\in\mathcal{H}_{n}$ be an element of finite order and let
$k\in\mathbb{N}$ be minimal such that ${A}^{\vee}_{k}$ is the zero of the
semigroup generated by the dual. Then (up to isomorphism of automata)
$\mathscr{A}({A}^{\vee}_{k})$ is the minimal strongly synchronizing automaton
admitting an automorphism $\phi$ of $G_{\mathscr{A}({A}^{\vee}_{k})}$ so that
$A$ is induced by $(\mathscr{A}({A}^{\vee}_{k}),\phi)$. Furthermore, $\phi$ is
the automorphism $\phi_{A}$ of Theorem 3.5.

###### Proof.

Let $A\in\mathcal{H}_{n}$ be finite order of order $o(A)$. We note that by
results in [15, 4] $k$ is minimal such that all of the elements
$A,A^{2},\ldots,A^{o(A)-1}$ are strongly synchronizing at level $k$ ($A^{i}$
being the product in $\mathcal{H}_{n}$ of $A$ with itself $i$ times).

It follows from Theorem 3.5 that $\mathscr{A}({A}^{\vee}_{k})$ is an automaton
supporting $A$ and indeed that $(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$
induces $A$. We argue below that $\mathscr{A}({A}^{\vee}_{k})$ is a minimal
such automaton, and further, that any minimal automaton supporting $A$ is
isomorphic to a folding of $\mathscr{A}({A}^{\vee}_{k})$, and hence, must
actually be $\mathscr{A}({A}^{\vee}_{k})$ up to isomorphism.

Now suppose that there was another automaton $B$, such that $A$ acts as an
automorphism $\psi_{A}$ of the underlying digraph of $B$ so that
$H(B,\psi_{A})$ has minimal representative $A$. Additionally suppose that $B$
is a minimal strongly synchronizing transducer on which $A$ acts as an
automorphism. We note that the minimal synchronizing level $l$ of $B$ is
greater than or equal to $k$ for, $H(B,\psi_{A}^{i})$ is strongly
synchronizing at level $l$ and has minimal representative $A^{i}$.

Suppose for a contradiction that $B\neq\mathscr{A}({A}^{\vee}_{k})$. There are
two cases.

Firstly for any state $q\in Q_{B}$, there is a state $p\in Q_{A}$ such that
the set $W(q,j)$ of words of length $j$ which force $q$ is contained in the
set $W(p,j)$ of words of length $j$ which force the state $p$ of
$\mathscr{A}({A}^{\vee}_{k})$. In this case, one observes that
$\mathscr{A}({A}^{\vee}_{k})$ is a folding of $B$ contradicting the minimality
of $B$.

Thus we must be in the negation of the first case. That is, we assume that
there is a pair of words $\gamma,\delta\in X_{n}^{k}$ such that the state of
$B$ forced by $\gamma$ is the same as the state of $B$ forced by $\delta$ but
$\gamma$ and $\delta$ force different states of $\mathscr{A}({A}^{\vee}_{k})$.
We may further assume that the states $[\gamma],[\delta]$ of
$\mathscr{A}({A}^{\vee}_{k})$ also satisfy
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\gamma])=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\delta])$.
This is because if
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\gamma])\neq\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\delta])$,
then we may find a word $\nu\in X_{n}^{+}$ such that
$[\gamma^{\prime}]:=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\nu,[\gamma])\neq\pi_{\mathscr{A}({A}^{\vee}_{k})}(\nu,[\delta])=[\delta^{\prime}]$,
satisfy
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\gamma^{\prime}])=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,[\delta]^{\prime})$.
Thus $\gamma\nu$ and $\delta\nu$ force the same state of $B$ but force,
respectively, the states $[\gamma^{\prime}]$ and $[\delta^{\prime}]$ of
$\mathscr{A}({A}^{\vee}_{k})$. We may then replace $\gamma,\delta$ with
$\gamma^{\prime},\delta^{\prime}$.

Let $z_{1}$ be the state of $B$ forced by $\gamma$ and $\delta$ and let
$z_{1},z_{2},\ldots,z_{o(A)}$ be the orbit of $z_{1}$ under the action of $A$.
As $H(B,\psi_{A})=H(\mathscr{A}({A}^{\vee}_{k}),\phi_{A})$, it must be the
case that if $a,b\in X_{n}$ are such that the edge $([\gamma],a,[\Gamma])$
maps to $(([\gamma])A,b,([\Gamma])A)$, then the edge $([\delta],a,[\Gamma])$
also maps to $(([\delta])A,b,([\Gamma])A)$. Thus we conclude that
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,([\gamma])A)=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,([\delta])A)$.
Now observe that since $\gamma$ and $\delta$ are representatives of $[\gamma]$
and $[\delta]$, respectively, and since for any $q\in Q_{A}$, the state of $B$
forced by $\lambda_{A}(\gamma,q)$ is equal to the state of $B$ forced by
$\lambda_{A}(\delta,q)$ is equal to $z_{2}$, it follows that there are
representatives of $([\gamma])A$ and $([\delta])A$ respectively such that the
states of $B$ forced by these representative is $z_{2}$. We may thus repeat
the argument in the $z_{1}$ case. By induction we therefore see that for any
$1\leq i\leq o(A)$, the points $([\gamma])A^{i}$ and $([\delta])A^{i}$ satisfy
that
$\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,([\gamma])A^{i})=\pi_{\mathscr{A}({A}^{\vee}_{k})}(\cdot,([\delta])A^{i})$
and whenever there are $a,b\in X_{n}$, such that $(([\gamma])A^{i},a,\nu)$ is
an edge mapping under $A$ to the edge $(([\gamma])A^{i+1},b(\nu)A$, then the
edge $(([\delta])A^{i}),a,\nu)$ also maps under $A$ to
$(([\delta])A^{i+1}),b,(\nu)A)$. This contradicts Lemma 3.7. $\Box$

##  4 Water for the witch – shrinking conjugacy class representatives

Suppose we have a finite order element $A\in\mathcal{H}_{n}$, induced by
$(B,\phi_{A})$ for some strongly synchronizing $B$ with a minimal number of
states. Under certain conditions we may employ a two-step process to find a
new element $C\in\mathcal{H}_{n}$, where $C$ is conjugate to $A$, and $C$ is
induced by $(D,\psi)$ for some strongly synchronizing $D$ with $D$ having
fewer states than $B$. In what follows we describe this process of finding
“smaller” conjugacy class representatives of $A$.

The first (and main) step in this process is to employ “relabelling.” This is
a conjugacy which, for a pair of states that would be identified in the
collapse sequence of the domain automaton, relabels inputs and outputs on
edges from this pair of states, with the goal of making this pair of states
represent the same local map. If this is possible, then we can collapse the
carrying transducer to a smaller one than we started with.

The conditions for a successful relabelling include that the orbits of these
states have the same lengths, and that for any two corresponding outgoing
edges, these orbit lengths of these edges are also the same. In the case where
some of these orbit lengths differ, then in certain circumstances we can
employ the second step of the overall process. This step“fluffs up” the
carrying automaton by executing some splittings, creating what we call _shadow
states_ , and where we can then employ relabelling to the result. In either
case, after a relabelling, the whole resultant transducer can be minimised so
as to be carried by a transducer with strictly fewer states than $T_{A}$.

In the case that $A$ is conjugate to an $n$-cycle this process will eventually
result in single state transducer representing an $n$-cycle.

###  4.1 Relabellings and automata sequences

######  Definition 4.1.

Let $A$ be a strongly synchronizing automaton and $A=A_{0},A_{1},\ldots,A_{m}$
be a collapse chain of $A$. Let $0\leq k\leq m$ and $\phi_{k}$ be a vertex
fixing automorphism of $G_{A_{k}}$. Define $A^{\prime}$ to be the automaton
with $Q_{A^{\prime}}=Q_{A}$ and transition function defined as follows: for
$p\in Q_{A}$, set $\pi_{A^{\prime}}(x^{\prime},p)=q$ if and only if there is
an $x\in X_{n}$ such that $\pi_{A}(x,p)=q$ with
$\lambda_{H(A_{k},\phi_{k})}(x,[p])=x^{\prime}$. We call $A^{\prime}$ the
_relabelling of $A$ by $(A_{k},\phi_{k})$_ or _the relabelling of $A$ by (the
transducer) $H(A_{k},\phi_{k})$_.

Note that if we relabel $A$ by $(A_{k},\phi_{k})$, then the resulting
automaton $A^{\prime}$ is strongly isomorphic to $A$ in the sense that there
is a natural digraph isomorphism from the underlying digraph of $A^{\prime}$
to the underlying digraph of $A$ that fixes states and which maps the
relabelled edges of $A^{\prime}$ to the original edges in $A$. More precisely,
if $(p,x,q)$ is an edge of $G_{A}$ and
$\lambda_{H(A_{k},\phi_{k})}(x,[p])=x^{\prime}$, then the natural digraph
isomorphism maps the edge $(p,x^{\prime},q)$ of $A^{\prime}$ to the edge
$(p,x,q)$ of $A$. The point of view one should have in mind is that we have
renamed/relabelled the edges of $A$ by switching edge labels on edges which
are parallel edges in $A_{k}$. Notice that if we relabel by
$(A_{0},\phi_{0})$, then all we do is switch labels on parallel edges in $A$,
thus the resulting underlying digraph would not change, but a “fixed” drawing
of it would be relabelled.

######  Lemma 4.2.

Let $A$ be a strongly synchronizing automaton and $A=A_{0},A_{1},\ldots,A_{m}$
be a collapse chain for $A$. Let $0\leq k\leq m$ and $\phi$ be a vertex fixing
automorphism of $G_{A_{k}}$. Let $A^{\prime}$ be the relabelling of $A$ by
$(A_{k},\phi)$. Then $A^{\prime}$ has underlying digraph strongly isomorphic
to the underlying digraph of $A$ and $A_{m}$ remains a folding of
$A^{\prime}$. More specifically, writing
$A^{\prime}=A^{\prime}_{0},A^{\prime}_{1},\ldots,A^{\prime}_{l}$ for the
collapse chain from $A^{\prime}$ to $A_{m}$, then $l\leq m$ and two states of
$u,v$ of $A$ belong to the same state of $A_{i}$ if and only if for some
$i^{\prime}\leq i$ we have $u$ and $v$ belong to the same state of
$A^{\prime}_{i^{\prime}}$.

###### Proof.

We may consider $A$ as a non-minimal synchronizing transducer where each state
induces the identity transformation of the set $X_{n}$. Consider the core of
the product $A\ast H(A_{k},\phi)$. Let $p\in Q_{A}$, and $\gamma\in X_{n}^{+}$
be such that the state of $A$ forced by $\gamma$ is $p$. Then, by definition
of $A_{k}$, the state of $A_{k}$ forced by $\gamma$ is the state $[p]$
containing $p$. Thus the set of states of
$\mathop{\mathrm{core}}\nolimits(A\ast H(A_{k},\phi))$ is the set
$\\{(p,[p])\mid p\in Q_{A}\\}$. Let $x\in X_{n}$ and $p,q\in Q_{A}$ such that
$\pi_{A}(x,p)=q$. Then we have, $\pi_{A}(x,(p,[p]))=(q,[q])$ and
$\lambda_{A}(x,(p,[p]))=\lambda_{H(A_{k},\phi)}(x,[p])$. Thus setting
$A^{\prime}$ to be the output automaton of
$\mathop{\mathrm{core}}\nolimits(A\ast H(A_{k},\phi))$ we see that
$A^{\prime}$ is the relabelling of $A$ by $(A_{k},\phi)$. From this it follows
that the underlying digraph of $A^{\prime}$ is strongly isomorphic to the
underlying digraph of $A$.

Let $u,v$ be two states of $A$ which belong to the same state of $A_{m}$ and
which transition identically on all words of length $j$ and suppose $j$ is
minimal for which this happens. Let $p\in Q_{A}$ be an arbitrary state and let
$W(p)\subseteq X_{n}^{j}$ consist of those words $\gamma$ such that
$\pi_{A}(\gamma,u)=\pi_{A}(\gamma,v)=p$. We break into cases based on whether
or not $k\geq j$ or $k<j$.

First suppose that $k\geq j$. This means that in $A_{k}$, the states $[u]$ and
$[v]$ are equal. Thus,
$\lambda_{H(A_{k},\phi)}(\gamma,[u])=\lambda_{H(A_{k},\phi)}(\gamma,[v])$ for
any $\gamma\in X_{n}^{*}$. Therefore in $A^{\prime}$ we see that the set of
words $\nu\in X_{n}^{j}$ for which
$\pi_{A^{\prime}}(\nu,u)=\pi_{A^{\prime}}(\nu,v)=p$ is precisely the set
$\\{\lambda_{H(A_{k},\phi)}(\gamma,[u])\mid\gamma\in W(p)\\}$.

Now suppose that $k<j$. This means that the states $[u]$ and $[v]$ are
distinct states of $A_{k}$ such that $\pi_{A_{k}}(\cdot,[u])$ and
$\pi_{A_{k}}(\cdot,[v])$ coincide on $X_{n}^{j-k}$. Let $\gamma\in W(p)$ be
arbitrary. Set $\gamma_{1}$ to be the length $j-k$ prefix of $\gamma$ and set
$\gamma_{2}\in X_{n}^{k}$ such that $\gamma_{1}\gamma_{2}=\gamma$. Set
$[r]=\pi_{A_{k}}(\gamma_{1},[u])=\pi_{A_{k}}(\gamma_{1},[v])$ and set
$\kappa\in X_{n}^{k}$ such that
$\lambda_{H(A_{k},\phi}(\kappa,[r])=\gamma_{2}$. For $t\in\\{u,v\\}$, set
$\delta_{t}\in X_{n}^{j-k}$ be such that
$\lambda_{H(A_{k},\phi)}(\delta_{t},[t])=\gamma_{1}$. Then since $\phi$ is a
vertex fixing automorphism of $A_{k}$ we notice that $\pi_{A}(\delta_{u},u)$,
$\pi_{A}(\delta_{v},v)$, $\\{\pi_{A}(\gamma_{1},t)\mid t\in\\{u,v\\}\\}$ all
belong to the same state of $A_{k}$. This means that
$\pi_{A}(\kappa,\pi_{A}(\delta_{u},u))=\pi_{A}(\kappa,\pi_{A}(\delta_{v},v))=s$.(Note
that $[s]=[p]$ in $A_{k}$ by the vertex fixing property of $\phi$.) Therefore
$\pi_{A\ast H(A_{k},\phi)}(\delta_{u}\kappa,(u,[u]))=(s,[p])=\pi_{A\ast
H(A_{k},\phi)}(\delta_{v}\kappa,(v,[v]))$. Since $\lambda_{A\ast
H(A_{k},\phi)}(\delta_{u}\kappa,(u,[u]))=\gamma=\lambda_{A\ast
H(A_{k},\phi)}(\delta_{v}\kappa,(v,[v]))$, we see that in $A^{\prime}$,
$\pi_{A^{\prime}}(\gamma,u)=\pi_{A^{\prime}}(\gamma,v)$.

Therefore, in $A^{\prime}$, $\pi_{A^{\prime}}(\cdot,u)$ and
$\pi_{A^{\prime}}(\cdot,v)$ coincide on the set $W(p)$. Since $p$ was chosen
arbitrarily and $\sqcup_{p\in Q_{A}}W(p)=X_{n}^{j}$ we conclude that
$\pi_{A^{\prime}}(\cdot,u)$ and $\pi_{A^{\prime}}(\cdot,v)$ coincide on the
set $X_{n}^{j}$.

The result now follows by Theorem 2.8.

Now suppose that there are states $u,v$ of $A$ which belong to the same state
$A^{\prime}_{i^{\prime}}$ for some $0\leq i^{\prime}\leq l$. Then since $u,v$
belong to the same state of $A_{m}$, there is an $i$ between $0$ and $m$ such
that $u$ and $v$ belong to the same state of $A_{i}$. The preceding paragraph
and Theorem 2.8 show that $i^{\prime}$ must be less than or equal to $i$.
$\Box$

Let $A$ be a strongly synchronizing automaton and $A^{\prime}$ be the
relabelling of $A$ by $(A_{k},\phi_{k})$. Set $\iota:G_{A}\to G_{A^{\prime}}$
to be the natural digraph isomorphism. If $\varphi$ is an automorphism of the
underlying digraph $G_{A}$ of $A$, then we will mean by the induced
automorphism $\varphi^{\prime}$ of $G_{A^{\prime}}$ precisely the map
$\iota^{-1}\varphi\iota$.

######  Lemma 4.3.

Let $A\in\mathcal{H}_{n}$ be an element of finite order and let $B$ be a
strongly synchronizing automaton such that there is an automorphism $\phi_{A}$
of the underlying digraph of $B$ with $A$ the minimal representative of
$H(B,\phi_{A})$. Let $B_{k}$ be an element of the synchronizing sequence of
$B$ and $\psi$ a vertex fixing automorphism of $B_{k}$. Let $B^{\prime}$ be
the relabelling of $B$ according to $(B_{k},\psi)$ and $\varphi$ be the
induced isomorphism from the underlying digraph of $B$ to the underlying
digraph of $B^{\prime}$. Set $P$ to be the minimal representative of the
transducer $H(B,B^{\prime},\varphi)$. Then $P^{-1}AP$ is the minimal
representative of $H(B^{\prime},\phi_{A}^{\varphi})$.

###### Proof.

This is a straight-forward application of the definitions. $\Box$

In the situation of Lemma 4.3 we refer to the resulting transducer $P^{-1}AP$
as the _transducer induced from $A$ by the relabelling $B\mapsto B^{\prime}$_.

######  Lemma 4.4.

Let $A$ be a strongly synchronizing automaton, and let $s,t$ be distinct
states of $A$. Let $(A_{i})_{1\leq i\leq m}$ be a collapse chain of $A$ such
that $s,t$ belong to the same state of $A_{m}$. Let $1\leq k<m$ be minimal
such that $t$ belongs to the state $[s]$ of the automaton $A_{k+1}$. Then for
all $x,x^{\prime}\in X_{n}$ such that $\pi_{A}(x,s)=\pi_{A}(x^{\prime},t)$ and
$[v]\in\\{[s],[t]\\}$, states of $A_{k}$, we have
$\pi_{A_{k}}(x,[v])=\pi_{A_{k}}(x^{\prime},[v])$.

###### Proof.

By minimality of $k$, it must be the case that the states $[s]$ and $[t]$ of
$A_{k}$ are distinct and the equality
$\pi_{A_{k}}(\cdot,[s])=\pi_{A_{k}}(\cdot,[t])$ holds.

Let $x,x^{\prime}\in X_{n}$ and $u\in Q_{A}$ be such that
$\pi_{A}(x,s)=\pi_{A}(x^{\prime},t)=u$. Then by definition of $A_{k}$,
$\pi_{A_{k}}(x,[s])=[u]=\pi_{A_{k}}(x^{\prime},[t])$. However, the equality
$\pi_{A_{k}}(\cdot,[s])=\pi_{A_{k}}(\cdot,[t])$, now implies that
$\pi_{A_{k}}(x^{\prime},[s])=[u]=\pi_{A_{k}}(x,[t])$ also. $\Box$

####  4.1.1 Constructing discriminant permutations
$\mathop{\mathrm{disc}}(s,t,Q)$

Let $A$ be an automaton and let $s,t\in Q_{A}$. Set the notation:

$\displaystyle\mathop{\mathrm{E}}{\,\\!\\!}_{A}(s,t)$
$\displaystyle:=\\{(s,x,t)\in\textrm{E}_{A}\\};and$
$\displaystyle\mathop{\mathrm{Letters}}{\,\\!\\!}_{A}(s,t)$
$\displaystyle:=\\{x\in
X_{n}\mid(s,x,t)\in\mathop{\mathrm{E}}{\,\\!\\!}_{A}(s,t)\\}.$

We may leave out the explicit mention of the automaton $A$ when it is clear
from context, writing simply E$(s,t)$ and Letters$(s,t)$ for these sets in
this case.

Let $Q\subseteq Q_{A}$ and $s\in Q_{A}$. Set the notation

$X_{s,Q}:=\bigsqcup_{p\in Q}\mathop{\mathrm{Letters}}(s,p).$

Now, suppose $s,t\in Q_{A}$ and suppose further there is a subset $Q\subseteq
Q_{A}$ so that

  1. (a)

$X_{s,Q}=X_{t,Q}$, and

  2. (b)

for all $p\in Q$ we have
$\scalebox{1.2}{$|$}\mathop{\mathrm{Letters}}(s,p)\scalebox{1.2}{$|$}=\scalebox{1.2}{$|$}\mathop{\mathrm{Letters}}(t,p)\scalebox{1.2}{$|$}$
.

Then to describe this situation we say $s$ and $t$ distribute similarly over
$Q$. (Note in passing that for some choices of $s$ and $t$ the only possible
such set $Q$ may be empty.) For any states $s$ and $t$ and set $Q\subset
Q_{A}$ so that $s$ and $t$ distribute similarly over $Q$, we denote by $X_{Q}$
the set $X_{s,Q}=X_{t,Q}$. We call $X_{Q}\subseteq X_{n}$ the agreement
alphabet (of $s$ and $t$ on $Q$) noting that if $Q=Q_{A}$, then $X_{Q}=X_{n}$.

Define a bijection $\mathrm{disc}(s,t,Q):X_{Q}\to X_{Q}$ as follows.

First, let $p_{1},\ldots,p_{r}\in Q$ be a maximal sequence of distinct states
such that for $1\leq i\leq r$ there is an $x\in X_{Q}$ with
$\pi_{A}(x,s)=p_{i}$. Observe that the sets

$\\{\mathop{\mathrm{Letters}}(s,p_{i})\mid 1\leq i\leq r\\}$

and

$\\{\mathop{\mathrm{Letters}}(t,p_{i})\mid 1\leq i\leq r\\}$

form partitions of $X_{Q}$, with equal-size corresponding parts in index $i$.

Now, for $1\leq i\leq r$, set $\mathrm{disc}(s,t,Q)$ to act as the identity on
$\mathop{\mathrm{Letters}}(s,p_{i})\cap\mathop{\mathrm{Letters}}(t,p_{i})$.
Set

$\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}:=\mathop{\mathrm{Letters}}(s,p_{i})\backslash(\mathop{\mathrm{Letters}}(s,p_{i})\cap\mathop{\mathrm{Letters}}(t,p_{i}))$

and

$\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}:=\mathop{\mathrm{Letters}}(t,p_{i})\backslash(\mathop{\mathrm{Letters}}(s,p_{i})\cap\mathop{\mathrm{Letters}}(t,p_{i})).$

We note that
$|\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}|=|{\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}}|$
and indeed that

$Y_{s,t}:=\bigcup_{1\leq i\leq
r}\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}=\bigcup_{1\leq i\leq
r}\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}.$

Order the elements of $\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}$ and
$\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}$ with the order induced from
$X_{n}$. For $1\leq i\leq r$ and
$x\in\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}$ we write $x^{\prime}$ for
the corresponding element of $\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}$,
that is, in the ordering of $\mathop{\mathrm{Letters}}(s,p_{i})^{\prime}$ and
$\mathop{\mathrm{Letters}}(t,p_{i})^{\prime}$ induced from $X_{n}$, $x$ and
$x^{\prime}$ have the same index.

Using the definitions and facts above we extend the definition of
$\mathop{\mathrm{disc}}(s,t,Q)$ over the set $Y_{s,t}$ by the rule $x\mapsto
x^{\prime}$. One easily checks that the resulting function

$\mathop{\mathrm{disc}}(s,t,Q):X_{Q}\to X_{Q}$

is a well-defined bijection. Further, observe that for $x_{0}\in Y_{s,t}$ the
function $\mathop{\mathrm{disc}}(s,t,Q)$ contains a cycle $(x_{0}\ x_{1}\
x_{2}\ \ldots\ x_{k-1})$ in its disjoint cycle decomposition, where for all
$i$ we have $x_{i+1}=x_{i}^{\prime}$ (indices taken mod $k$). Recall as well
that $\mathop{\mathrm{disc}}(s,t,Q)$ acts as the identity over the set
$X_{Q}\backslash Y_{s,t}$.

For $s$ and $t$ satisfying points (b) and (b) for some set $Q$ we call
$\mathop{\mathrm{disc}}(s,t,Q)$ the discriminant of $s$ and $t$; it is a
permutation that encodes the difference in transitions between $s$ and $t$
amongst the set of states $Q$. In the case that $Q=Q_{A}$, we will write
$\mathop{\mathrm{disc}}(s,t)$ for the bijection
$\mathop{\mathrm{disc}}(s,t,Q_{A})$. As with the notation
$\mathop{\mathrm{Letters}}(p,q)$, we often run in to situations where we
compute discriminant permutations in distinct automata sharing the same state
set, in such cases we use the notation
$\mathop{\mathrm{disc}}{\,\\!\\!}_{A}(s,t,Q)$ and
$\mathop{\mathrm{disc}}(s,t)$ to emphasise the automaton in which the
permutation is computed.

######  Lemma 4.5.

Let $A$ be a strongly synchronizing automaton, and let $s,t$ be distinct
states of $A$. Let $Q\subseteq Q_{A}$ be such that $s$ and $t$ distribute
similarly over $Q$ with agreement alphabet $X_{Q}$. Let $(A_{i})_{1\leq i\leq
m}$ be a collapse chain of $A$ such that $s,t$ belong to the same state of
$A_{m}$. Let $1\leq k<m$ be minimal such that $\pi_{A_{k}}(\cdot,[t])$ and
$\pi_{A_{k}}(\cdot,[s])$ are equal on $X_{Q}$. Then for $x,y\in X_{Q}$ which
belong to the same disjoint cycle of $\mathop{\mathrm{disc}}(s,t,Q)$,

$\pi_{A_{k}}(x,[s])=\pi_{A_{k}}(y,[s])=\pi_{A_{k}}(y,[t])=\pi_{A_{k}}(x,[t]).$

###### Proof.

By assumption $\pi_{A_{k}}(\cdot,[s])=\pi_{A_{k}}(\cdot,[t])$.

An easy induction argument using the definition of
$\mathop{\mathrm{disc}}(s,t,Q)$ now shows that for any $x,y\in X_{n}$ such
that $y$ belongs to the orbit of $x$ under the action of
$\mathop{\mathrm{disc}}(s,t,Q)$,

$\pi_{A_{k}}(x,[s])=\pi_{A_{k}}(y,[s])=\pi_{A_{k}}(x,[t])=\pi_{A_{k}}(y,[t]).$

This follows since for any $x\in X_{n}$,
$\pi_{A}(x,s)=\pi_{A}((x)\mathop{\mathrm{disc}}(s,t,Q),t)$.

$\Box$

####  4.1.2 Discriminant permutations and amalgamation sequences

Let $B$ be an automaton and $G:=G_{B}$ be the underlying digraph of $B$.
Define a sequence $G:=G_{0},G_{1},\ldots$ as follows. Assuming $G_{i}$ is
defined, $G_{i+1}$ is obtained from $G$ in the following manner. Let $\sim$ be
the equivalence relation on the vertices $Q_{G_{i}}$ of $G_{i}$ that relates
two vertices $p,q$ precisely when for every vertex $t\in Q_{G_{i}}$ the number
of edges from $q$ to $t$ is precisely the number of edges from $p$ to $t$. If
$p\in Q_{G_{i}}$ write $[p]_{i+1}$ for the equivalence class of $p$ under the
relation $\sim$. Set $Q_{G_{i+1}}=\\{[p]_{i+1}\mid p\in Q_{G_{i}}\\}$. Now
suppose $p,q\in Q_{G_{i}}$ and enumerate those elements of $[q]_{i+1}$ which
have an incoming edge from a vertex in $[p]_{i+1}$ in some order as
$q_{1},q_{2},\ldots,q_{r}$. For $1\leq j\leq r$, let $k_{j}$ be the number of
edges from $p$ to $q_{j}$ and set $ec(i+1,p,q):=\sum_{1\leq j\leq r}k_{j}$.
Set $G_{i+1}$ to be the directed graph with vertices $Q_{G_{i+1}}$ and with
$ec(i+1,p,q)$ many edges from $[p]_{i+1}$ to $[q]_{i+1}$ for each $[p]_{i+1}$,
$[q]_{i+1}\in Q_{G_{i+1}}$.

We refer to the resulting sequence $G_{0}$, $G_{1}$, …, as defined above as
the _amalgamation sequence of $G$_ (see [17]). Note that for each natural $i$
the construction above induces an identification of the states of $G_{i}$ with
a partition of $B$. It follows that after finitely many steps, the
amalgamation sequence stabilises to a fixed digraph.

The lemma below says that for a given automaton $B$, there is a relabelling of
$B$ such that the synchronizing sequence coincides with the amalgamation
sequence.

######  Lemma 4.6.

Let $B$ be an automaton with underlying digraph $G$ and synchronizing sequence
$B=B_{0},B_{1},\ldots$. Let $G=G_{0},G_{1},\ldots$ be the amalgamation
sequence of $G$. Then there is a relabelling $D$ of $B$ such that if
$D=D_{0},D_{1},\ldots$ is the synchronizing sequence of $D$, the underlying
digraph of $D_{i}$ is $G_{i}$; in particular, the partition of the state set
of $B$ induced by $D_{i}$ is the same partition induced by $G_{i}$.

###### Proof.

Since $B$ is strongly synchronizing there is a minimal $l\in\mathbb{N}$ for
which $G_{l}=G_{l+1}$ and both have a single vertex with $n$ loops. We proceed
by induction on the amalgamation sequence.

We begin with the base case. Let $s,t\in Q_{B}$ be distinct such that $s$ and
$t$ belong to the same state of $G_{1}$. This means that $s$ and $t$
distribute similarly over $Q_{B}$. Suppose that $\mathop{\mathrm{disc}}(s,t)$
is not trivial.

Let $k\in\mathbb{N}$ be minimal such that $s$ and $t$ belong to the same state
of $B_{k+1}$. Note that since $\mathop{\mathrm{disc}}(s,t)$ is not trivial,
then $k\geq 1$. By Lemma 4.5, for any $x,y$ which belong to the same orbit
under $\mathop{\mathrm{disc}}(s,t)$,

$\pi_{B_{k}}(x,[s])=\pi_{B_{k}}(y,[s])=\pi_{B_{k}}(x,[t])=\pi_{B_{k}}(x,[t]).$

Let $\lambda_{B_{k}}$ be defined such that
$\lambda_{B_{k}}(\cdot,[q]):X_{n}\to X_{n}$ is trivial whenever $[q]$ is not
equal to $[t]$. We set
$\lambda_{B_{k}}(\cdot,[t])=\mathop{\mathrm{disc}}(s,t)^{-1}$. We note that
the transducer $B_{k}$ is induced by a vertex fixing automorphism of $B_{k}$.
Furthermore, for any pair $(u,v)\neq(s,t)$ such that $u,v$ belong to the same
state of $G_{1}$ and $\mathop{\mathrm{disc}}(u,v)$ is trivial, $[u]=[v]$ in
$B_{k}$.

Let $E$ be the relabelling of $B$ by the transducer $B_{k}$. Note that
$Q_{E}=Q_{B}$ and $G$ remains the underlying digraph of $E$. It therefore
follows that for any pair $u,v$ in $B$ which distribute similarly over
$Q_{B}$, $u,v$ still distribute similarly over $Q_{B}$ in $E$. If moreover,
$\mathop{\mathrm{disc}}{\,\\!\\!}_{B}(u,v)$ is trivial, then construction of
$\lambda_{B_{k}}$, means $\mathop{\mathrm{disc}}{\,\\!\\!}_{E}(u,v)$ remains
trivial. Lastly we note that $s,t$ distribute similarly over $Q_{B}$ in $E$,
and $\mathop{\mathrm{disc}}{\,\\!\\!}_{E}(s,t)$ is trivial.

Applying an induction argument, there is an automaton $E_{1}$ a relabelling of
$B$ such that for any pair $s,t\in Q_{B}$ which belong to the same state of
$G_{1}$, $\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{1}}(s,t)$ is trivial. In
particular, such $s,t$ satisfy, $\pi_{E_{1}}(\cdot,s)=\pi_{E_{1}}(\cdot,t)$.

Now assume by induction that there is a relabelling $E$ of $B$ with
synchronizing sequence $E=E_{0},E_{1},\ldots$ possessing the following
property: for $0\leq i\leq k<l$ two states $s,t\in Q_{B}$ belonging to the
same state of $G_{i}$ belong to the same state of $E_{i}$.

Let $s,t\in Q_{B}$ and suppose $s$ and $t$ belong to the same state of
$G_{k+1}$ but do not belong to the same state of $E_{k+1}$. We note that since
the underlying digraph of $E_{k}$ is the same as $G_{k}$ and they induce the
same partition of the state set $Q_{B}$, then $s$ and $t$ belong to distinct
states of $E_{k}$ and so to distinct states of $G_{k}$. The fact that $s$ and
$t$ belong to the same state of $G_{k+1}$ means that $[s]$ and $[t]$
distribute similarly over $Q_{E_{k}}$ but
$\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}([s],[t])$ is not trivial.

Let $k<j\leq l$ be minimal such that $s$ and $t$ belong to the same state of
$E_{j+1}$. By Lemma 4.5 once more, we have the equalities: for any $x,y$ which
belong to the same orbit under
$\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}([s],[t])$,

$\pi_{E_{j}}(x,[s])=\pi_{E_{j}}(y,[s])=\pi_{E_{j}}(x,[t])=\pi_{E_{j}}(x,[t]).$

Let $\lambda_{E_{j}}$ be defined such that
$\lambda_{E_{j}}(\cdot,[q]):X_{n}\to X_{n}$ is trivial whenever $[q]$ is not
equal to $[t]$. We set
$\lambda_{E_{j}}(\cdot,[t])=\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}([s],[t])^{-1}$.
We note that the transducer $E_{j}$ is induced by a vertex fixing automorphism
of $E_{j}$. Furthermore, for any pair $(u,v)\neq(s,t)$ such that $u,v$ belong
to the same state of $G_{k+1}$ and
$\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}([u],[v])$ is trivial, $[u]=[v]$ in
$E_{j}$.

Let $F$ be the relabelling of $E$ by the transducer $E_{j}$. Let
$F_{1},F_{2}\ldots$ be the synchronizing sequence of $F$.

Let $u,v\in Q_{B}$ belong to the same state of $G_{i}$ for some $0\leq i\leq
k<l$. Then by the inductive assumption and Lemma 4.2, $u,v$ belong to the same
state of $F_{i}$.

Let $u,v\in Q_{B}$ belong to the same state of $G_{k+1}$ and suppose that
$\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}(u,v)$ is trivial. Note that since
$\mathop{\mathrm{disc}}{\,\\!\\!}_{E_{k}}(u,v)$ and $[u],[v]$ distribute
similarly over $Q_{E_{k}}$, $[u]=[v]$ in $E_{k+1}$. Therefore, Lemma 4.2
implies that $[u]=[v]$ in $F_{k+1}$ as well.

Lastly observe that $[s]=[t]$ in $F_{k+1}$ by construction of
$\lambda_{E_{k}}$ and the fact that states which are identified in $E_{k}$
remain identified in $F_{k+1}$.

The result now follows by induction. $\Box$

###  4.2 Relabellings along orbits

For lemma below, we give stronger hypotheses than appear to be required as per
the following observation. Let $B$ be a strongly synchronizing automaton,
$\phi$ an automorphism of the underlying digraph $G_{B}$ of $B$, and, $s$ and
$p$ states of $B$. Every edge from $s$ to a state in the orbit of $p$ (under
the action of $\phi$) is on an orbit of length $N$ (when such an edge exists)
if and only if every edge from any state in the orbit of $s$ to a state in the
orbit of $p$ is on an orbit of length $N$ (when such an edge exists). We state
the lemma with the stronger hypotheses below to ease understanding.

######  Lemma 4.7.

Let $B$ be a strongly synchronizing automaton and $\phi$ an automorphism of
the underlying digraph $G_{B}$ of $B$. Let $s,p$ be vertices of $G_{B}$ so
that $\mathop{\mathrm{Letters}}{\,\\!\\!}_{B}(s,p)$ is non-empty. Suppose

  * •

there is $N\in\mathbb{N}_{1}$ so that for every edge $e$ from a vertex in the
orbit of $s$ to a vertex in the orbit of $p$, the orbit length of $e$ is $N$,
and secondly

  * •

there is $r\in\mathbb{N}_{1}$ so that if $(s\phi^{i},y,p\phi^{j})$ is any edge
from the orbit of $s$ to the orbit of $p$, then we have
$\mathop{\mathrm{Letters}}(s\phi^{i},p\phi^{j})=\mathop{\mathrm{Letters}}(s\phi^{i+r},p\phi^{j})$.

Then there is a relabelling of $B^{\prime}$ of $B$ such that the induced
automorphism $\phi^{\prime}$ of $G_{B^{\prime}}$ satisfies the following: for
any $i,j\in\mathbb{N}$,

  * •

$\mathop{\mathrm{Letters}}{\,\\!\\!}_{B^{\prime}}(s\phi^{i},p\phi^{j})=\mathop{\mathrm{Letters}}{\,\\!\\!}_{B^{\prime}}(s\phi^{i+r},p\phi^{j})$,
and,

  * •

if
$x\in\mathop{\mathrm{Letters}}{\,\\!\\!}_{B^{\prime}}(s\phi^{i},p\phi^{j})$,
then the labels of the edges $(s\phi^{\prime i},x,p\phi^{\prime
j})\phi^{\prime}$ and $(s\phi^{\prime i+r},x,p\phi^{\prime j})\phi^{\prime}$
are equal.

###### Proof.

We first set up some notational convenience. Given an edge $(u,x,v)$ of $B$,
with respect to this edge, we shall write $x\phi^{i}$ for the label of its
image $(u,x,v)\phi^{i}$ so that we have the equality
$(u,x,v)\phi^{i}=(u\phi^{i},x\phi^{i},v\phi^{i})$. Note that in general we do
not have an induced action of $\phi$ on $X_{n}$, but the notation will be
well-defined in the context of a base edge $(u,x,v)$ being understood.

Let $B$, $\phi$, $s$, $p$, $N$ and $r$ be as in the hypotheses, and assume $r$
is minimal. It follows that $r$ divides the orbit length of $s$ (by
minimality). Write $mr$ for the orbit length of $s$. Write
$s_{1},s_{2},\ldots,s_{mr}$ for the orbit of $s=s_{1}$ (we note that $mr|N$
and we make this explicit below).

Let $\widetilde{P}$ be those states $p^{\prime}$ in the orbit of $p$ which
have $\mathop{\mathrm{Letters}}(s,p^{\prime})$ non-empty. The set
$\widetilde{P}$ can be partitioned according to the orbits under the action of
$\phi^{mr}$, that is, two elements of $\widetilde{P}$ belong to the same part
if they belong to the same orbit. Choose $T\subset\widetilde{P}$ so that $T$
has exactly one representative from each block of this partition. Note, by
definition, for any edge $(s(\phi^{r})^{i},x^{\prime},p\phi^{j})$,
$i,j\in\mathbb{N}$, there is a unique $p^{\prime\prime}\in T$ and an element
$x\in\mathop{\mathrm{Letters}}(s,p^{\prime\prime})$ so that the orbit of
$(s,x,p^{\prime\prime})$ under $\phi^{r}$ contains
$(s(\phi^{r})^{i},x^{\prime},p\phi^{j})$.

We inductively define a map $\lambda_{B}$ (i.e., induced by a vertex fixing
automorphism of $B$) along the orbit of an edge $(s,x,q)$ for some $q\in T$.
The map $\lambda_{B}$ will then determine a transducer
$(X_{n},Q_{B},\pi_{B},\lambda_{B})$ which can be used (as in Definition 4.1)
to carry out the required relabelling. To this end fix $q\in T$ and set
$k=|\\{q\phi^{imr}|i\in\mathbb{N}\\}|$.

For $0\leq a\leq m-1$, partition $\mathop{\mathrm{Letters}}(s_{ar+1},q)$ via
the equivalence relation relating two edge labels whose corresponding edges
are in the same orbit under $\phi^{kmr}$. Recall there is an order on the
elements of each equivalence class induced from the standard $\leq$ ordering
on $X_{n}$. Use this ordering to determine a transversal for the equivalence
classes, choosing as representative of each class the least element in that
class. Write $\beta(s_{ar+1})$ for this transversal. For $b\in\beta(s_{ar+1})$
we use the phrase the equivalence class of $b$ at $s_{ar+1}$ to mean the edge
labels in $\mathop{\mathrm{Letters}}(s_{ar+1},q)$ which are orbit equivalent
to $b$.

Let $0\leq a,a^{\prime}\leq m-1$. We note that since N is the orbit length of
any edge from a state in the orbit of $s$ to a state in the orbit of $q$ we
have $|\beta(s_{ar+1})|=|\beta(s_{a^{\prime}r+1})|$. Let $\alpha\in\mathbb{N}$
such that for $b\in\beta(s_{ar+1})$ and
$b^{\prime}\in\beta(s_{a^{\prime}r+1})$, the size of the equivalence class of
$b$ at $s_{ar+1}$ is equal to the size of the equivalence class of
$b^{\prime}$ at $s_{a^{\prime}r+1}$ is equal to $\alpha$. We fix a bijection
between the sets $\beta(s_{ar+1})$ and $\beta(s_{a^{\prime}r+1})$ induced by
the ordering of the elements. We note that $\alpha kmr=N$.

For $1\leq j\leq r$, and $0\leq a\leq m-1$ we write $\beta(s_{ar+j})$ for the
set $\\{b\phi^{j-1}|b\in\beta(s_{ar+1})\\}$. We note that the orbit
equivalence class of $b\phi^{j-1}$ at $s_{ar+j}$, $b\in\beta(s_{ar+1})$, is
precisely the image of the equivalence class of $b$ at $s_{ar+1}$ under the
image of $\phi^{j-1}$. We transport using $\phi^{j-1}$ the orderings of
$\beta(s_{ar+1})$, and the equivalence classes of elements
$b\in\beta(s_{ar+1})$ to the set $\beta(s_{ar+j})$ and the equivalence classes
of its elements. That is, for instance, if $b<b^{\prime}\in\beta(s_{ar+1})$,
then $b\phi^{j-1}<b^{\prime}\phi^{j-1}$ in $\beta(s_{ar+j})$.

Let $1\leq l\leq m$ be minimal such that
$\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{rl}=\\{q\phi^{imr}|i\in\mathbb{N}\\}$.
We note that by minimality $l|m$ since:
$\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{mr}=\\{q\phi^{imr}|i\in\mathbb{N}\\}$.
Moreover
$\phi^{lr}:\\{q\phi^{imr}|i\in\mathbb{N}\\}\to\\{q\phi^{imr}|i\in\mathbb{N}\\}$
is a $k$-cycle since
$\phi^{mr}:\\{q\phi^{imr}|i\in\mathbb{N}\\}\to\\{q\phi^{imr}|i\in\mathbb{N}\\}$
is a $k$-cycle and $\phi^{mr}$ is a power of $\phi^{lr}$. Let $M\in\mathbb{N}$
be such that $Ml=m$ so that $\alpha kMlr=N$.

Further observe that if
$\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{rd}\cap\\{q\phi^{imr}|i\in\mathbb{N}\\}\neq\emptyset$
for some $d\in\mathbb{N}$, then
$\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{rd}=\\{q\phi^{imr}|i\in\mathbb{N}\\}$.
For suppose $q\phi^{fmr}\in\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{rd}$ for some
$1\leq f\leq k$. Then there is some $1\leq j\leq k$ such that
$q\phi^{jmr}\phi^{dr}=q\phi^{fmr}$, this now means that
$q\phi^{dr}\phi^{jmr}\in\\{q\phi^{imr}|i\in\mathbb{N}\\}$. However since
$\phi^{mr}$ is a $k$-cycle on the set $\\{q\phi^{imr}|i\in\mathbb{N}\\}$, then
$q\phi^{dr}\in\\{q\phi^{imr}|i\in\mathbb{N}\\}$.

Thus we conclude that the sets $\\{q\phi^{imr}|i\in\mathbb{N}\\}\phi^{ar}$ for
$0\leq a\leq l-1$ are pairwise disjoint.

We define a relabelling map $\lambda_{B}$ inductively as follows.

Let $b=b_{0}\in\beta(s_{1})$ be the smallest element such that
$\lambda_{B}(b,s)$ is undefined and for all $1\leq i\leq l-1$
$\lambda_{B}(b_{i},s_{ir+1})$ is undefined for the element $b_{i}$ of
$\beta(s_{ir+1})$ corresponding to $b$. (Note that $b_{i}$ is the least
element of $\beta(s_{ir+1})$ such that $\lambda_{B}(b_{i},s_{ir+1})$ that is
undefined.) In the inductive process which follows, we will define
$\lambda_{B}(b_{i},s_{ir+1})$ for all $0\leq i\leq l-1$ in order.

Define a $kl$-by-$r$ matrix $\mathfrak{r}$ with entries tuples of size
$\alpha$ as follows. Set

$\mathfrak{r}_{0,0}=(b=b_{1,1},b_{1,2},\ldots,b_{1,\alpha})$

where $(b_{1,1},\ldots,b_{1,\alpha})$ is the ordered tuple of element
$\beta(s_{1})$. For $0\leq i<kl$ and $0\leq j<r$ set
$\mathfrak{r}_{i,j}=(b_{1,1},b_{1,2},\ldots,b_{1,\alpha})\phi^{ir+j}=(b_{1,1}\phi^{ir+j},b_{1,2}\phi^{ir+j},\ldots,b_{1,\alpha}\phi^{ir+j})$.

Define a matrix $\mathfrak{R}$ of dimension $Mkl$-by-$r$ such that
$\mathfrak{R}_{i,j}$ for $0\leq i<Mkl$ and $0\leq j<r$ has entry

$((b_{1,1},s),\ldots,(b_{1,\alpha},s))\phi^{ir+j}:=((b_{1,1}\phi^{ir+j},s\phi^{ir+j}),\ldots,(b_{1,\alpha}\phi^{ir+j},s\phi^{ir+j})).$

For $0\leq d<M$, set $\mathfrak{R}(d)$ to be the $kl$-by-$r$ matrix
corresponding to rows $dkl$ to row $(d+1)kl-1$. For $0\leq d<M$, $0\leq i<kl$
and $0\leq j<r$ we set $\lambda_{B}\mathfrak{R}(d)_{i,j}=\mathfrak{r}_{i,j}$,
where we extend $\lambda_{B}$ naturally to act on tuples $(X_{n}\times
Q_{B})^{\alpha}$ to produce tuples in $X_{n}^{\alpha}$.

Let $1\leq i<l$. We note that for the element $b^{\prime}\in\beta_{s_{ir+1}}$,
the function $\lambda_{B}(b^{\prime},s_{ir+1})$ remains undefined. Let the
matrix $\mathfrak{r}$ be exactly as above and define the matrix $\mathfrak{R}$
as above but with $b^{\prime}$ playing the role of $b$ and $s_{ir+1}$ playing
the role of $s_{1}=s$. For $0\leq d<M$ define the component $\mathfrak{R}(d)$
as above. Then once more for $0\leq d<\alpha M$, $0\leq i<kl$ and $0\leq j<r$
we set $\lambda_{B}\mathfrak{R}(d)_{i,j}=\mathfrak{r}_{i,j}$.

Continuing on in this way across the set $T$, we define $\lambda_{B}$ on all
pairs $(x,s\phi^{i})$ where $i\in\mathbb{N}$ and there is a $j\in\mathbb{N}$
such that $(s\phi^{i},x,p\phi^{j})$ is an edge. We set $\lambda_{B}$ to be
projection onto the first coordinate on all other pairs in $X_{n}\times
Q_{B}$.

By construction $\lambda_{B}$ is induced by a vertex fixing automorphism and
induces the required relabelling of $B$.

$\Box$

######  Remark 4.8.

Note that the relabelling $B^{\prime}$ of $B$ given by Lemma 4.7 is in fact
isomorphic as an automaton to $B$, since the relabelling is by a vertex fixing
automorphism of $B$. This means we may instead write $(B,\phi)$ for the pair
$(B^{\prime},\phi^{\prime})$.

######  Lemma 4.9.

Let $B$ be a strongly synchronizing automaton and $\phi$ an automorphism of
the underlying digrpah $G_{B}$ of $B$. Let $s,t,p$ be states of $B$ such that
there is an $x\in X_{n}$ with $\pi_{B}(x,s)=p$. Suppose

  * •

for $i,j\in\mathbb{N}$, $\pi_{B}(x,s\phi^{i})=p\phi^{j}$ if and only if
$\pi_{B}(x,t\phi^{i})=p\phi^{j}$;

  * •

the orbits of $s$ and $t$ are distinct and have equal length $l$;

  * •

there is an $N\in\mathbb{N}$ such that for any $j\in\mathbb{N}$, all edges
$(s,x,p\phi^{j})$ and $(t,x,p\phi^{j})$ are on orbits of length $N$.

Then there is a relabelling of $B^{\prime}$ of $B$ such that the induced
automorphism $\phi^{\prime}$ of $G_{B^{\prime}}$ satisfies: for any
$i,j\in\mathbb{N}$
$\mathop{\mathrm{Letters}}(s\phi^{i},p\phi^{j})=\mathop{\mathrm{Letters}}(t\phi^{i},p\phi^{j})$,
and for any $x\in\mathop{\mathrm{Letters}}(s\phi^{i},p\phi^{j})$, the labels
of the edges $(s\phi^{i},x,p\phi^{j})\phi^{\prime}$ and
$(t\phi^{i},x,p\phi^{j})\phi^{\prime}$ coincide.

###### Proof.

This is a more straight-forward relabelling operation than the previous case.
We simply match the orbits of $t$ along $p$ with those of $s$ along $p$. We
define the relabelling map $\lambda_{B}$ inductively. As before, throughout we
observe the following notation. Let $u,v\in Q_{B}$ and $x\in X_{n}$ such that
$(u,x,v)$ is an edge. For $i\in\mathbb{N}$ we write $x\phi^{i}$, whenever
there is no ambiguity, for the label of the edge $(u,x,v)\phi^{i}$.

First, for any pair $(c,d)\in X_{n}\times Q_{B}$ such that $(d,c,\pi(c,d))$ is
not an edge from a state in the orbit of $t$ to a state in the orbit of $p$,
set $\lambda_{B}(c,d)=c$.

Let $x\in X_{n}$ be smallest such that $(t,x,p\phi^{i})$ is an edge for some
$i$ and $\lambda_{B}(x,t)$ is not defined. Let $y\in X_{n}$ be minimal such
that $(s,y,p\phi^{i})$ is an edge and $y$ is not equal to $\lambda_{B}(z,t)$
for $(t,z,p\phi^{i})$ an edge. For $0\leq j<N$ set
$\lambda_{B}(x\phi^{j},t\phi^{j})=y\phi^{j}$ where $y\phi^{j}$ is the label of
the edge $(s,y,p\phi^{i})\phi^{j}$.

This inductively defined relabelling map $\lambda_{B}$ is given by a vertex
fixing automorphism and induces the required relabelling of $B$.

$\Box$

######  Remark 4.10.

We note that, once more, $B^{\prime}$ and $B$ are isomorphic as automata and
so we may write $(B,\phi^{\prime})$ for $(B^{\prime},\phi^{\prime})$.

###  4.3 Shadow states

In this second part of our process, we find new states to add to the
transducer via splitting operations, to provide more room for relabelling.

Let $A\in\mathcal{H}_{n}$ have finite order and let $B$ be a minimal strongly
synchronizing automaton such that there is an automorphism $\phi_{A}$ of the
underlying digraph $G_{B}$ of $B$ with $A$ the minimal representative of
$H(B,\phi_{A})$.

The following definition is motivated by considering paths into a vertex $t$
that might provide an obstruction to a collapse through relabelling of $B$, as
described in the next paragraph.

Suppose there is a state $q$ of $B$ so that there is a minimal length $r$ so
that all paths of length $r$ that end on $q$ have orbits of length $n$ under
the action of $\phi_{A}$, and for this choice of $q$ we have $r>1$. Let
$\mathcal{P}=e_{1}e_{2}\ldots e_{r}$ be a path of length $r$ terminating at
$q$, where the orbit of $\mathcal{P}$ has length $n$ but the orbit of
$e_{2}e_{3}\ldots e_{r}$ is of size $c$ for some $c<n$. For indices $1\leq
i\leq j\leq r$ set $\mathcal{P}_{i,j}:=e_{i}e_{i+1}\ldots e_{j}$. By
construction, the least common multiple of the orbit size of the edge $e_{1}$
and of $c$ is $n$, and further, the orbit length of $\mathcal{P}_{2,r-1}$ must
divide $c<n$. As will become clear later, if this situation arises, it may be
an obstruction to collapse of a transducer through a relabelling process.

In the definition that follows, the state $t$ corresponds to the target of
$e_{1}$ from the path $\mathscr{p}$ mentioned above, while $b$ is some integer
multiple of the orbit length of $t$, but which still properly divides $n$.

######  Definition 4.11.

Let $A\in\mathcal{H}_{n}$, $B$ be a minimal strongly synchronizing automaton
such that there is an automorphism $\phi_{A}$ of the underlying digraph
$G_{B}$ of $B$ with $A$ the minimal representative of $H(B,\phi_{A})$, and
$t\in Q_{B}$. We say _$t$ is heavy (for the pair $(B,\phi_{A})$)_ if the
following conditions hold:

  * •

there is a proper divisor $b$ of $n$, where $b$ is divisible by the length of
the orbit of $t$;

  * •

there is at least one pair $(x,s)\in X_{n}\times Q_{B}$ such that $(s,x,t)$ is
an edge;

  * •

for any $x\in X_{n}$ and any $s\in Q_{B}$ such that $(s,x,t)$ is an edge of
$B$, the lowest common multiple of $b$ and the length of the orbit of
$(s,x,t)$ under $\phi_{A}$ is $n$.

In this case, we call the value $b$ above a _divisibility constant for $t$_
and observe that the set of valid divisibility constants for $t$ might have
more than one element.

In our overall process, we will apply the Lemma 4.13 (directly below) in a
situation where we cannot simplify a transducer $H(B,\phi_{A})$ directly by a
relabelling operation. Specifically, this lemma is useful in situations where
we can carry out an in-split of the domain automaton $B$ along the orbit of a
heavy state $t$ to create a new automaton $B^{\prime}$ with automorphism
$\psi_{A}$ so that $A$ is a minimal representative of both $H(B,\phi_{A})$ and
of $H(B^{\prime},\psi_{A})$, and where the new pair $(B^{\prime},\psi_{A})$
has a reduced obstruction to the existence of a helpful relabelling. Note that
here, we mean “in-split” in the normal sense of that operation for edge-shift
equivalences, see, e.g. [11].

The following lemma characterises how to perform an _in-split along the orbit
of a heavy state $t$_. The new automaton that is created has all of the old
states, together with new states which we call _shadow states (from the orbit
of $t$)_.

The following two lemmas address the same set of hypotheses, but we split the
results into two statements as the lemma of primary interest is the second
one.

Any such number $n^{\prime}$ which arises as in Lemma 4.12 below will be
referred to as a _valid splitting length for (the heavy state) $t$ with
respect to divisibility constant $b$._

######  Lemma 4.12.

Let $A\in\mathcal{H}_{n}$ and let $B$ be a minimal strongly synchronizing
automaton such that there is an automorphism $\phi_{A}$ of the underlying
digraph $G_{B}$ of $B$ with $A$ the minimal representative of $H(B,\phi_{A})$.
Suppose there are $b\in\mathbb{N}$ and $t\in Q_{B}$ so that $t$ is heavy for
the pair $(B,\phi_{A})$ with $b$ a divisibility constant for $t$, and where
$\big{|}\\{t\phi_{A}^{p}|p\in\mathbb{Z}\\}\big{|}=r$.

In these circumstances, there is $n^{\prime}\in\mathbb{N}$ a number which
divides the lengths of orbits of all edges $(s,x,t)$ and satisfies the
following conditions:

  1. i)

the lowest common multiple of $n^{\prime}$ and $b$ is $n$,

  2. ii)

there is $m>1$ so that $n^{\prime}=mr$.

###### Proof.

Let $N$ be the greatest common divisor of the orbit lengths of all edges
$(s,x,t)$ in $B$. Let $(s,x,t)$ be an edge of $B$ with orbit length $k$ under
the action of $\langle\phi_{A}\rangle$. Now, by the third bullet point of the
definition of the state $t$ being heavy we see that
$\operatorname{lcm}(k,b)=n$. It follows, as $(s,x,t)$ is an arbitrary incoming
edge for $t$, that $\operatorname{lcm}(N,b)=n$ as well. Since $r$ is the orbit
length of $t$ we see that $r|k$ and since $(s,x,t)$ is an arbitrary incoming
edge for $t$ we therefore have $r|N$. By assumption, $r|b$, so if $r=N$ we
would have $\operatorname{lcm}(N,b)=b<n$ which is a contradiction. It then
follows that $N=kr$ for some integer $k>1$. Thus the set of numbers $N$ which
divide the orbit lengths of all edges $(s,x,t)$ and satisfy points i) and ii)
is non-empty. Now let $n^{\prime}$ be an element of this set and determine
$m\in\mathbb{N}$ so that $mr=n^{\prime}$ (noting that $1<m$ by construction).
$\Box$

######  Lemma 4.13.

Let $A\in\mathcal{H}_{n}$ and let $B$ be a minimal strongly synchronizing
automaton such that there is an automorphism $\phi_{A}$ of the underlying
digraph $G_{B}$ of $B$ with $A$ the minimal representative of $H(B,\phi_{A})$.
Suppose there is $b\in\mathbb{N}$ and $t\in Q_{B}$ so that $t$ is heavy for
the pair $(B,\phi_{A})$ with $b$ a divisibility constant for $t$. Set
$t_{0,0}=t$ and let $t_{0,0},t_{0,1}\ldots,t_{0,r-1}$ be the orbit of $t$
under iteration by $\phi_{A}$. Let $n^{\prime}$ be a valid splitting length of
$t$ and let $m>1$ be determined by $n^{\prime}=mr$.

In these circumstances we may form a new strongly synchronizing automaton
$B^{\prime}$ with

$Q_{B^{\prime}}=Q_{B}\sqcup\\{t_{a,0},\ldots,t_{a,r-1}\mid 1\leq a<m\\}$

such that we have

  1. i)

$\pi_{B^{\prime}}(x,s):=\pi_{B}(x,s)$ for those pairs $(x,s)\in X_{n}\times
Q_{B}$ where $\pi_{B}(x,s)$ is not in the orbit of $t$;

  2. ii)

$\pi_{B^{\prime}}(\cdot,t_{a,i}):=\pi_{B^{\prime}}(\cdot,t_{0,i})$ for all
$0\leq a<m$, $0\leq i<r$;

  3. iii)

The incoming transitions of $B^{\prime}$ to the set of vertices
$\\{t_{a,i}\mid 0\leq a<m,0\leq i<r\\}$ are determined by the above rules, and
by an automorphism $\psi_{A}$ of the underlying digraph $G_{B^{\prime}}$ of
$B^{\prime}$ satisfying: $(t_{0,0})\psi_{A}^{ar+i}=t_{a,i}$ for $0\leq a<m$,
$0\leq i<r$, $(t_{0,0})\psi_{A}^{n^{\prime}}=t_{0,0}$, and
$H(B^{\prime},\psi_{A})=A$.

###### Proof.

Let $n^{\prime}$ be a valid splitting length for the heavy state $t_{0,0}$
with divisibility constant $b$, and let $m>1$ be an integer so that
$n^{\prime}=mr$.

Set

$T:=\\{t_{0,0},t_{0,1},\ldots,t_{0,r-1}\\}$

and build a set of new objects (the extra “shadow states” arising from the
splitting along the orbit of $t_{0,0}$)

$T^{\prime}=\\{t_{a,1},t_{a,2},\ldots,t_{a,r}\mid 1\leq a<m\\}.$

Note that $|T\cup T^{\prime}|=n^{\prime}$.

We will define an action $\psi_{A}$ on

$Q_{B^{\prime}}:=Q_{B}\cup T^{\prime}$

as follows.

For $s\in Q_{B^{\prime}}$, set

$s\psi_{A}=\left\\{\begin{matrix}[l]s\phi_{A}&\textrm{ if }&s\in
Q_{B}\backslash T&\\\ t_{a,i+1}&\textrm{ if }&s=t_{a,i}\textrm{ and }i<r-1&\\\
t_{a+1,0}&\textrm{ if }&s=t_{a,r-1}\textrm{ and }a<m-1&\\\ t_{0,0}&\textrm{ if
}&s=t_{m-1,r-1}.&\end{matrix}\right.$

It is immediate by construction that this is an action, and also that the
orbit of $t_{0,0}$ has size $n^{\prime}$. We will specify transitions for
$B^{\prime}$ by steadily expanding the definition of the underlying digraph
$G_{B^{\prime}}$ of $B^{\prime}$ through adding edges of the form $(p,x,q)$
for $p,q\in Q_{B^{\prime}}$ and $x\in X_{n}$ (thus adding the transition
$(x,p)\pi_{B^{\prime}}=q$ to $B^{\prime}$), while simultaneously extending the
function $\psi_{A}$ on the corresponding edges of $G_{B^{\prime}}$.
Ultimately, $B^{\prime}$ will be a strongly synchronizing automaton and
$\psi_{A}$ will be an automorphism of the digraph $G_{B^{\prime}}$ with
$H(B^{\prime},\psi_{A})$ being equivalent to $A$.

Important in what follows will be a graph homomorphism
$\iota:G_{B^{\prime}}\to G_{B}$, which we will automatically extend to the
(new) edges of $G_{B^{\prime}}$ whenever they are added. On the set
$Q_{B^{\prime}}$, $\iota$ is defined as follows: for $s\in
Q_{B^{\prime}}\backslash(T\cup T^{\prime})$ set $s\iota:=s$, and for any
$t_{a,i}\in T\cup T^{\prime}$ set $t_{a,i}\iota:=t_{0,i}$.

Below, whenever we extend $G_{B^{\prime}}$ by adding new edges, we also extend
the graph homomorphisms $\iota:G_{B^{\prime}}\to G_{B}$ and
$\psi_{A}:G_{B^{\prime}}\to G_{B^{\prime}}$ so as to maintain _rsc_ , the
_rule of semi-conjugacy_ , which we define here.

rsc

:

  1. (a)

for all $q\in Q_{B^{\prime}}$ we have $q\psi_{A}\iota=q\iota\phi_{A}$, and

  2. (b)

for all edges $e$ of $G_{B^{\prime}}$ we further require
$e\psi_{A}\iota=e\iota\phi_{A}$.

Of course we have part (a) of the rule because we have already defined $\iota$
and $\psi_{A}$ over $Q_{B^{\prime}}$ to satisfy this rule.

In the above construction of $\iota$ if $e\iota=(r,x,s)$ then we will identify
$e$ as $(p,x,q)$ where $p$ is the source of $e$ and $q$ is the target of $e$,
so after any extension we can always think of the new $G_{B^{\prime}}$ as an
edge-labelled directed graph with edge labels “lifted” from $G_{B}$ by the map
$\iota$.

Note that below we will sometimes add a large collection of edges at one go,
but in this case, there is always a well defined triple $(p,x,q)$ for each new
edge, as we add in edges along an orbit under $\psi_{A}$ which always contains
a well-defined edge $(r,y,s)$, from which we can detect the correct letter
labelling of all edges along the orbit by using rsc.

It follows that if $B^{\prime}$ is a strongly synchronizing automaton then
$H(B,\phi_{A})$ will represent the same element of $\mathcal{H}_{n}$ as
$H(B^{\prime},\psi_{A})$, since the map $\iota$ never changes edge labels, and
the map $\psi_{A}$ will have to change edge labels in the corresponding
fashion as $\phi_{A}$ in order to uphold rsc.

We now begin to specify the edges of $G_{B^{\prime}}$, and hence the
transition function $\pi_{B^{\prime}}$. Recall below that $Q_{B}\backslash
T=Q_{B^{\prime}}\backslash(T\cup T^{\prime})$.

Partition the edges of $G_{B}$ into the following four sets.

$\displaystyle N_{T}:=$ $\displaystyle\\{(p,x,q)\mid p,q\not\in T\\},$
$\displaystyle B_{T}:=$ $\displaystyle\\{(p,x,q)\mid p,q\in T\\},$
$\displaystyle D_{T}:=$ $\displaystyle\\{(p,x,q)\mid p\in T,q\not\in
T\\},\textrm{ and}$ $\displaystyle R_{T}:=$ $\displaystyle\\{(p,x,q)\mid
p\not\in T,q\in T\\}.$

We observe in passing that $\phi_{A}$ acts on each of the sets $N_{T}$,
$B_{T}$, $D_{T}$, and $R_{T}$.

For $(p,x,q)$ an edge in $N_{T}$, let $(p,x,q)$ also be an edge of
$G_{B^{\prime}}$ (and so $(x,p)\pi_{B^{\prime}}=q$ as well) and set
$(p,x,q)\psi_{A}:=(p,x,q)\phi_{A}$.

Recall that for a group $H$ acting on a set $X$, a traversal for the orbits is
a subset $\mathscr{Y}\subset X$ so that each orbit under the group action has
a unique representative in the set $\mathscr{Y}$.

Let $\mathscr{Y}_{B}$ be a traversal for the orbits of the edges in $B_{T}$
such that each edge in $\mathscr{Y}_{B}$ is of the form $(t_{0,0},x,t_{0,i})$.
Similarly set $\mathscr{Y}_{D}$ to be a traversal for the orbits of the edges
in $D_{T}$ so that each edge of $\mathscr{Y}_{D}$ is of the form
$(t_{0,0},x,s)$ for some $s\in Q_{B}\backslash T$. Finally set
$\mathscr{Y}_{R}$ to be a traversal for the orbits of the edges in $R_{T}$ so
that each edge of $\mathscr{Y}_{R}$ is of the form $(s,x,t_{0,0})$ for some
$s\in Q\backslash T$.

Extend $G_{B^{\prime}}$ to include
$\mathscr{Y}_{D}\cup\mathscr{Y}_{R}\cup\mathscr{Y}_{B}$ as edges incident on
$t_{0,0}$ (we will add more edges incident on $t_{0,0}$ later). Furthermore,
use the action of $\psi_{A}$ on the set $Q_{B^{\prime}}$ together with the map
$\iota$ to uniquely determine new edges (of the form $(p,x,q)$ for $x\in
X_{n}$) that must be added to $G_{B^{\prime}}$ so that the resulting digraph
is closed under the action of $\psi_{A}$, contains the transversal edges
$\mathscr{Y}_{D}\cup\mathscr{Y}_{R}\cup\mathscr{Y}_{B}$ and satisfies rsc.
Note that this process extends the definition of $\iota$ and $\psi_{A}$ to
these new edges as well, but these extensions are inductively well defined.
Now we may use the new edges of $G_{B^{\prime}}$ in the obvious way to also
extend the definition of the transition function $\pi_{B^{\prime}}$ so as to
create a correspondingly larger automaton $B^{\prime}$.

Observe that for any state $s\in Q_{B^{\prime}}\backslash(T\cup
T^{\prime})=Q_{B}\backslash T$, the process above now has created a unique
edge of the form $(s,x,q)$ for each $x\in X_{n}$ (which are the “lifts” of
$N_{T}$ and $R_{T}$ to $G_{B^{\prime}}$ by $\iota$). For edges in $N_{T}$ this
is simply by definition. For an edge $(s,x,t_{0,i})\in R_{T}$, there is an
edge $(s^{\prime},x^{\prime},t_{0,0})\in\mathscr{Y}_{R}$ so that there is a
minimal non-negative integer $k$ with
$(s^{\prime},x^{\prime},t_{0,0})\phi_{A}^{k}=(s,x,t_{0,i})$. It follows that
$(s^{\prime},x^{\prime},t_{0,0})\psi_{A}^{k}=(s,x,t_{a,i})$ for the unique
non-negative $a$ so that $k=ar+i$. Now suppose there is an edge
$(s,x,t_{b,j})$ of $G_{B^{\prime}}$. By rsc, we see that
$(s,x,t_{b,j})\iota=(s,x,t_{0,j})$ but as there is a unique outgoing edge in
$G_{B}$ from $s$ with letter $x$ we see that $t_{0,j}=t_{0,i}$ and in
particular, $i=j$. We assume without meaningful loss of generality that $b\geq
a$ and that $|b-a|$ is minimal amongst all such differences. Thus by rsc the
orbit length of the edge $(s,x,t_{0,i})$ under $\phi_{A}$ is precisely
$(b-a)r$ or else $b=a$. However, $(b-a)r<n^{\prime}$ and $n^{\prime}$ divides
the length of the orbit of $(s,x,t_{0,i})$ by the definition of $n^{\prime}$.
It follows that $(s,x,t_{a,i})$ is the unique pre-image of $(s,x,t_{0,i})$
under $\iota$.

There remains a special concern that we must address. Specifically, there are
now pairs $(x,t_{a,i})\in X_{n}\times(T\cup T^{\prime})$ so that there are no
edges of the form $(t_{a,i},x,q)$ in $G_{B^{\prime}}$. This happens as the
orbit of $t_{0,0}$ has length $r$ under $\phi_{A}$ but length
$n^{\prime}=mr>r$ under $\psi_{A}$. Also, to verify the coherence of the rsc
condition for edges in $\mathscr{Y}_{B}$, recall that $n^{\prime}$ divides the
orbit length of these edges as they are in the orbit of an edge incident to
$t$.

Let us now deal with the “missing edges” issue. Observe that for an edge
$(t_{0,0},x,s)\in\mathscr{Y}_{D}\cup\mathscr{Y}_{B}$, its orbit under
$\phi_{A}$ may contain multiple edges of the form $(t_{0,0},y,q)$ (for various
$y\in X_{n}$ and $q\in Q_{B}$). Let us organise these as the sequence of
pairwise distinct edges $(e_{0},e_{1},\ldots,e_{k})$ where
$e_{i}=(t_{0,0},x,s)\phi_{A}^{ri}$, and with
$e_{k}\phi_{A}^{r}=e_{0}=(t_{0,0},x,s)$. In this context, the orbit of
$(t_{0,0},x,s)$ under $\phi_{A}$ has length $(k+1)r$. Let us set notation
$e_{i}=:(t_{0,0},x_{i},q_{i})$ so we can understand the letter $x_{i}$
associated to $e_{i}$ for each valid index $i$. The concern is that in our
current graph $G_{B^{\prime}}$ we see for any index $0<i\leq k$ that there is
no edge of the form $(t_{0,0},x_{i},q)\in G_{B^{\prime}}$. For the letter
$x_{i}$ observe that there is an edge of the form $(t_{a,0},x_{i},q_{i})$ of
$G_{B^{\prime}}$ for $a=ir\mod n^{\prime}$ and some state $q_{i}$. The rule of
modification is, add the edge $(t_{0,0},x_{i},q_{i})$ to $G_{B^{\prime}}$, for
all indices $0<i\leq k$. Repeat this same procedure across all of the
transversal elements
$(t_{0,0},x^{\prime},s^{\prime})\in\mathscr{Y}_{D}\cup\mathscr{Y}_{B}$ and as
a consequence, for each letter $y\in X_{n}$, we see that the vertex $t_{0,0}$
now has a unique outgoing edge of the form $(t_{0,0},y,q)$. Finally, we again
use the action of $\psi_{A}$ on vertices and the action of $\phi_{A}$ on
$G_{B}$ along with the rsc condition to extend the definitions of $\psi_{A}$
and $\iota$ to the necessary edges we have to add to $G_{B^{\prime}}$ in order
to complete the orbits of our newly-added edges based at $t_{0,0}$, and to
discern what letters needed to be associated to these new edges. Now induce
from $G_{B^{\prime}}$ the enlarged automaton $B^{\prime}$.

One observes that for any valid indices $a$ and $b$ and fixed index $i$, the
states $t_{a,i}$ and $t_{b,i}$ of $B^{\prime}$ have all the same outgoing
transitions, and indeed, that the automaton $B^{\prime}$ collapses back down
to $B$ by identifying these states for each fixed $i$. In particular
$G_{B^{\prime}}$ is strongly synchronizing as it admits a collapse sequence to
the $n$-leafed rose. Further, the rsc condition implies that $\psi_{A}$ acts
as an automorphism of the directed graph $G_{B^{\prime}}$ in fashion locally
emulating how $\phi_{A}$ acts on $G_{B}$ so that $H(G_{B^{\prime}},\psi_{A})$
represents $A$.

$\Box$

Let $A,B,t=t_{0,0}$ be as in the statement of Lemma 4.13. Assume we applied
Lemma 4.13 to lengthen the orbit of $t$ as in the lemma statement to create
automaton $B^{\prime}$ with automorphism $\psi_{A}$ so that
$H(B^{\prime},\psi_{A})$ has minimal representative $A$ and where the orbit of
$t$ in $G_{B^{\prime}}$ under the action of $\psi_{A}$ is the set
$\\{t_{a,i}\mid 0\leq a<m,0\leq i<r\\}$. Now for each state $t_{0,i}$ for
$0\leq i<r$ (these states are in the original orbit of $t$ in $G_{B}$ under
the action of $\phi_{A}$), we call the set of states

$\\{t_{a,i}\mid 0<a\leq m-1\\}\subsetneq Q_{B^{\prime}}$

the shadow states for $t_{0,i}$ (in $Q_{B^{\prime}}$). Note that these are
precisely the states of $H(B^{\prime},\psi_{A})$ with local maps equivalent to
the local map at $t_{0,i}$ for the transducer $H(B,\phi_{A})$. If we apply
Lemma 4.13 inductively and perhaps repeatedly on states on the now extended
orbit of $t$, we extend the definition of the shadow states of $t_{0,i}$ to be
the union of the sets of states added in each round of applying Lemma 4.13
which have local maps equivalent to the local map at $t_{0,i}$ for the
transducer $H(B,\phi_{A})$. Note that this process cannot go on forever as
each application of Lemma 4.13 lengthens the orbit of $t_{0,0}$ with $n$ an
upper bound on the length of this orbit. Also note that each added state will
be a shadow state of one of the original states $t_{0,j}$ after any number of
iterated applications of Lemma 4.13.

######  Lemma 4.14.

Let $A\in\mathcal{H}_{n}$ and let $B$ be the minimal strongly synchronizing
automaton such that there is an automorphism $\phi_{A}$ of the underlying
digraph of $B$ with $A$ the minimal representative of $H(B,\phi_{A})$. Suppose
that all circuits in $B$ are on orbits of length $n$ under the action of $A$.
Then there is a strongly synchronizing transducer $\widehat{B}$ such that $A$
acts as an automorphism $\widehat{\psi}_{A}$ of $\widehat{B}$ and all edges of
$\widehat{B}$ are on orbits of length $n$ under the action of $A$.

###### Proof.

We first observe that all states of $B$ must be on orbits of length dividing
$n$ as the underlying digraph of $B$ is strongly synchronizing and therefore
each state is visited by some circuit which is on an orbit of length $n$.
Also, we may assume that $|B|>1$ otherwise all loops at the state of $B$ will
be on orbits of length $n$ and we would be done.

Let $s\in Q_{B}$ be such that $s$ is on an orbit of length strictly less than
$n$ under $\phi_{A}$. (If all states of $Q_{B}$ were on orbits of length $n$
then all edges of $B$ would be on orbits of length $n$ as well and we would be
done.)

Inductively define states as follows.

Set $Q_{B}(0,s):=\\{s\\}$. Assume $Q_{B}(i,s)$ is defined for some
$i\in\mathbb{N}$. We now define $Q_{B}(i+1,s)\subseteq Q_{B}$. An element
$q\in Q_{B}$ belongs to $Q_{B}(i+1,s)$ if the following conditions hold:

  1. (a)

there are elements $x_{1},x_{2},\ldots,x_{i+1}\in X_{n}$, such that, for all
$1\leq j\leq i+1$, we have $\pi_{B}(x_{i+1}\ldots x_{j},q)\in Q_{B}(j-1,s)$;
and

  2. (b)

the path $(q,x_{i+1}x_{i}\ldots x_{1},s)$ is on an orbit of length strictly
less than $n$ under $\phi_{A}$.

We observe that for any state $q$ in a set $Q_{B}(i+1,s)$, the orbit of $q$
under $\phi_{A}$ has size properly dividing $n$. If $q\in Q_{B}(i+1,s)$ and
$x_{i+1},x_{i},\ldots,x_{1}\in X_{n}$ satisfies points (a) and (b) then we
call the path $(q,x_{i+1}x_{i}\ldots x_{1},s)$ _conformant for
$Q_{B}(i+1,s)$_.

Let $k\in\mathbb{N}$ be minimal so that $Q_{B}(k+1,s)=\emptyset$. If such $k$
did not exist then there would a long path (as in point (b) of the definition
of the sets $Q_{B}(i,s)$) which is long enough that it must contain a circuit
in $B$. Any such circuit would be on an orbit of length strictly less than $n$
under the action of $\phi_{A}$, which is a contradiction.

From the argument directly above it also follows that whenever $j>0$, $s\notin
Q_{B}(j,s)$.

We now apply an induction argument using Lemma 4.13 to reduce $k$ to $0$.

Let $t\in Q_{B}(k,s)$ and fix $x_{k},x_{k-1},\ldots,x_{1}\in X_{n}$, such that
the path $(t,x_{k}x_{k-1}\cdots x_{1},s)$ is conformant for $Q_{B}(k,s)$ and
where the orbit of this path under the action of $\phi_{A}$ is of length $b<n$
(note that $b|n$ and also that the length of the orbit of $t$ divides $b$).
Moreover, by choice of $k$, for any pair $(x,p)\in X_{n}\times Q_{B}$ with
$\pi_{B}(x,p)=t$, the lowest common multiple of the length of the orbit of the
edge $(p,x,t)$ and $b$ is $n$.

Therefore $t$ is heavy for the pair $(B,\phi_{A})$ and $b$ is a divisibility
constant for $t$, so we may apply Lemma 4.13 with the state $t$ and constant
$b$ to add states in the orbit of $t$ and necessary edges to form a new
strongly synchronizing automaton $B^{\prime}$ with $\psi_{A}$ an automorphism
of $G_{B^{\prime}}$, and so that $H(B^{\prime},\psi_{A})$ still represents $A$
(and so in particular, all circuits of $G_{B^{\prime}}$ are still on orbits of
length $n$ under the action of $\psi_{A}$).

Recall that by the construction of $B^{\prime}$, the orbit of $t$, which
includes all of its shadow states, is now of larger size $n_{t}^{\prime}$
under the action of the resulting digraph automorphism $\psi_{A}$. Thus, for
any $t^{\prime}$ in the orbit of $t$ (including the shadow states we have just
added), if there is a path from $t^{\prime}$ to $s$ which is conformant for
$Q_{B^{\prime}}(k,s)$, then $t^{\prime}$ (and therefore $t$) is heavy for
$(Q_{B^{\prime}},\psi_{A})$, so we may again inductively increase the length
of the orbit of $t$ by adding more shadow states until there are no paths from
a point in the orbit of $t$ to $s$ which are conformant for
$Q_{B^{\prime}}(k,s)$ (note this happens to be a consequence of $t$ no longer
being heavy for $(B^{\prime},\psi_{A})$ which must happen eventually as the
orbit of $t$ is getting longer and is bounded above by $n$). Note that if
$p\in Q_{B^{\prime}}(k,s)$ but $p$ is not in the orbit of $t$, then $p\in
Q_{B}(k,s)$. In particular, we have $|Q_{B^{\prime}}(k,s)|<|Q_{B}(k,s)|$ as
this count of states for $B^{\prime}$ no longer includes the state $t$ nor any
state in its orbit.

We can now inductively repeat this process for $s$ until
$|Q_{B^{\prime}}(k,s)|=0$.

Note that we can repeat this process for any state $p$ with
$|Q_{B^{\prime}}(k,p)|\neq 0$. Thus we may now proceed inductively in this
fashion until finally we have constructed an automaton $B^{\prime}$ and an
automorphism $\psi_{A}$ of $G_{B^{\prime}}$ so that $B^{\prime}$ folds onto
$B$ and $H(B^{\prime},\psi_{A})$ represents $A$, and where if $q$ is any state
and $j$ is minimal so that $Q_{B^{\prime}}(j,q)=\emptyset$, then $j=0$.

We set $\widehat{B}=B^{\prime}$ and $\widehat{\psi}_{A}=\psi_{A}$ in this
final case, noting that the orbit of every edge of $\widehat{B}$ under the
action of $\widehat{\psi}_{A}$ is of length $n$.

$\Box$

######  Remark 4.15.

Let $A\in\mathcal{H}_{n}$ be an element of finite order and suppose that every
point in $X_{n}^{-\mathbb{N}}$ is on an orbit of length $n$ under the action
of $A$. By lemma 4.14, there is a minimal (in size) strongly synchronizing
automaton $B$ such that $A$ acts as an automorphism $\phi_{A}$ of the
underlying digraph of $B$ and all edges of $B$ are on orbits of length $n$
under the action of $A$.

###  4.4 Relabelling through shadows

In this section we make use of Lemma 4.13 to deal with situations in which we
are unable to directly apply Lemma 4.7 or Lemma 4.9.

The lemma below says that applying Lemma 4.13 and then suitably relabelling
does not move us out of the conjugacy class of the considered finite order
element $A\in\mathcal{H}_{n}$.

######  Definition 4.16.