# Automorphisms of the two-sided shift and the Higman–Thompson groups III:
extensions

Feyishayo Olukoya

###### Abstract

A key result of the article Automorphisms of shift spaces and the
Higman–Thompson groups: the two-sided case [3] is that the group of
automorphisms of the two-sided dynamical system
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ is a central
extension by a subgroup $\mathcal{L}_{n}$ of the outer-automorphism group
$\mathcal{O}_{n}$ of the Higman–Thompson group $G_{n,n-1}$.

The current article builds on the results of [3] by further establishing
connections between the groups
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ and
$\mathcal{O}_{n}$. Our key aims are to interpret several important
constructions in the theory of automorphisms of the shift dynamical system in
terms of the group $\mathcal{L}_{n}$ and secondly to extend results and
techniques in $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to the
groups $\mathop{\mathrm{Aut}}({G_{n,r}})$ of automorphisms of the
Higman–Thompson group $G_{n,r}$ and their outerautomorphism groups
$\mathcal{O}_{n,r}\cong\mathop{\mathrm{Out}}({G_{n,r}})$.

Our mains results are a concrete realisation of the inert subgroup, an
important subgroup in the study of the groups
$\mathop{\mathrm{Aut}}({X_{n}^{*},\sigma_{n}})$, as a subgroup
$\mathcal{K}_{n}$ of $\mathcal{L}_{n}$ using the technology developed in [3].

Using the realisation above, and by passing to a subgroup $\mathcal{D}_{n}$ of
$\mathcal{K}_{n}$ which lifts as a subgroup of
$\mathop{\mathrm{Aut}}({G_{n,r}})$ for all $1\leq r\leq n-1$, we show that the
$\mathop{\mathrm{Aut}}({G_{n,r}})$ contains an isomorphic copy of
$\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})$ for all $m\geq 2$. A
quick survey of the literature then yields that
$\mathop{\mathrm{Aut}}({G_{n,r}})$ contains isomorphic copies of finite
groups, finitely generated abelian groups, free groups, free products of
finite groups, fundamental groups of 2-manifolds, graph groups and countable
locally finite residually finite groups [17] to name a few. Another
consequence of the embedding is that both $\mathop{\mathrm{Aut}}({G_{n,r}})$
and $\mathop{\mathrm{Out}}({G_{n,r}})$ have undecidable order problem. We note
that the result for $\mathop{\mathrm{Out}}({G_{n,r}})$ is proved in [3] using
a slightly different method.

Lastly, we extend a fairly straight-forward result for
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to the groups
$\mathcal{O}_{n,r}$. The homeomorphism $\overleftarrow{\phantom{a}}$, an
involution, of $X_{n}^{\mathbb{Z}}$ which maps a sequence
$(x_{i})_{i\in\mathbb{Z}}$ to the sequence $(y_{i})_{i\in\mathbb{Z}}$ defined
such that $y_{i}=x_{-i}$ induces by conjugation an automorphism
$\overleftarrow{\mathfrak{r}}$ of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, and consequently, an
automorphism of $\mathcal{L}_{n}$. We extend the automorphism
$\overleftarrow{\mathfrak{r}}$ to the group $\mathcal{O}_{n}$. As there is, to
our knowledge, no index preserving action of $\mathcal{O}_{n}$ on
$X_{n}^{\mathbb{Z}}$, the extension to $\mathcal{O}_{n}$ requires a different
proof. Our proof is combinatorial in nature and relies on the faithful
representation of $\mathcal{O}_{n}$ in the permutation group on the set of
equivalence classes of prime words under rotational equivalence.

In a forthcoming article, we demonstrate that the group $\mathcal{O}_{n}$ is
isomorphic to the mapping class group of the full two-sided shift over $n$
letters.

##  1 Introduction

A key result of the article [3] is that the group of automorphisms of the two-
sided dynamical system
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ is a central
extension by a subgroup $\mathcal{L}_{n}$ of the outer-automorphism group
$\mathcal{O}_{n}$ of the Higman–Thompson group $G_{n,n-1}$. It is also shown
in [5] that the extension splits precisely when $n$ is not a power of a
strictly smaller integer.

The current article builds on the results of [3] by further establishing
connections between the groups
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ and
$\mathcal{O}_{n}$. Our key aims are to interpret several important
constructions in the theory of automorphisms of the shift dynamical system in
terms of the group $\mathcal{L}_{n}$ and secondly to extend results in
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to the groups
$\mathop{\mathrm{Aut}}({G_{n,r}})$ of automorphisms of the Higman–Thompson
group $G_{n,r}$ and their outerautomorphism groups $\mathcal{O}_{n,r}$.

Relative to the first aim our main results are as follows.

First we note briefly that elements of the group $\mathcal{L}_{n}$, and
related subgroups $\mathcal{L}_{n,r}=\mathcal{L}_{n}\cap\mathcal{O}_{n,r}$,
are finite state machines satisfying called transducers which satisfy a strong
synchronizing condition. Moreover all states of an element of
$\mathcal{L}_{n}$ induce continuous and injective maps on the Cantor space
$X_{n}^{\mathbb{N}}$ of infinite sequences in the alphabet $X_{n}$. Thus, we
may speak of the image of a state. For a word $\nu\in X_{n}^{*}$, the subset
of $X_{n}^{\mathbb{N}}$ consisting of all elements with a prefix $\nu$ is open
and the collection of all such open sets forms a basis for the Cantor space
$X_{n}^{\mathbb{N}}$. Write $\mathcal{K}_{n}\leq\mathcal{L}_{n}$ for the set
of those elements $T\in\mathcal{L}_{n}$ such that the image of a state (and
consequently any state) of $T$ is a union of a power of $n$ basic open sets.
By results in [3], $\mathcal{K}_{n}$ is in fact a subgroup of
$\mathcal{L}_{n,1}$ and, consequently, a subgroup of $\mathcal{L}_{n,r}$ for
any $1\leq r\leq n-1$ (using the inclusion
$\mathcal{O}_{n,1}\leq\mathcal{O}_{n,r}$ [4])

Our first result draws a connection to the inert subgroup of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ which is the kernel
of the dimension representation [18, 12]. Briefly, the dimension
representation is a map $\mathfrak{d}_{n}$ from
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}}})$ to the finitely generated
abelian group $\mathbb{Z}^{r-1}$ where $r$ is the number of prime divisors of
$n$.

Our result can be stated as follows:

######  Theorem 1.1.

Let $n$ be a natural number bigger than $2$. Let $p_{1},p_{2},\ldots,p_{r}$ be
distinct prime numbers and let $l_{1},l_{2},\ldots,l_{r}$ be elements of
$\mathbb{N}_{1}$ such that $n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}$
and set $l=\gcd(l_{1},l_{2},\ldots,l_{r})$. Then:

  1. a.

$\mathcal{K}_{n}\cong\mathrm{Inert}_{n}$

  2. b.

$\mathcal{L}_{n}\cong\mathcal{K}_{n}\rtimes(\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z})$

  3. c.

$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}}})\cong\mathcal{K}_{n}\rtimes\mathbb{Z}^{r}$

We prove this result by extending a homomorphism
$\overrightarrow{\mathrm{sig}}$ (see [19, 3]) from $\mathcal{L}_{n}$ unto the
subgroup $\mathfrak{U}_{n,n-1}$ of the group of units of $\mathbb{Z}_{n-1}$
generated by the divisors of $n$, to a map
$\overrightarrow{\mathrm{sig}}_{\omega}$ from $\mathcal{L}_{n}$ unto the group
$\mathfrak{M}(n)$ defined as the quotient of the submonoid of $\mathbb{N}$
generated by the prime divisors of $n$ by a certain congruence. This
congruence relates two elements of the submonoid where one is a power of $n$
times the other. The resulting quotient monoid is a finitely generated abelian
group isomorphic to $\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z}$ where
$n=p_{1}^{L_{1}}p_{2}^{L_{2}}\ldots p_{r}^{L_{r}}$ for distinct prime numbers
$p_{i}$ and $l=\gcd(l_{1},\ldots,l_{r})$. In particular we may write
$\mathcal{L}_{n}=\mathcal{K}_{n}\times(\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z})$
where $\mathcal{K}_{n}$ is the kernel of the homomorphism
$\overrightarrow{\mathrm{sig}}_{\omega}$. This decomposition is similar to
well known results about the quotient of the group
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ by the kernel
$\mathrm{Inert}_{n}$ of the _dimension representation_ , the _inert subgroup_.
We note that in that decomposition, we have
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})=\mathrm{Inert}_{n}\rtimes\mathbb{Z}^{r}$
where $r$ is the number of prime divisors of $n$ ([18, 12]). Using the fact
that $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ embeds naturally
into the group
$\mathop{\mathrm{Aut}}({X_{n^{m}}^{\mathbb{Z}},\sigma_{n^{m}}})$ for
$m\in\mathbb{N}$ and lifting the homomorphism from $\mathcal{L}_{n}$ to
$\mathfrak{U}_{n,n-1}$ one obtains a homomorphism from
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ into the group
$\Pi_{k\in\mathbb{N}}\mathfrak{U}_{n^{k},n^{k-1}}$. The kernel of this
homomorphism turns out to be isomorphic to the group $\mathcal{K}_{n}$ and in
this way we obtain Theorem 1.1. We should mention that the description of the
group $\mathcal{K}_{n}$ given above is known also to Belk and Bleak using
different methods [2].

Theorem 1.1 paves the way for accomplishing our second aim by yielding a means
of concretely realising and identify elements of the inert subgroup. Taking
advantage of this new realisation, we revisit various marker constructions
existing in the literature ([9, 10, 20, 15, 11]). We show that there is a
combinatorially defined infinite index subgroup $\mathcal{D}_{n}$ of
$\mathcal{K}_{n}$ such that elements of $\mathcal{K}_{n}$ arising from the
marker constructions in the articles above cited give rise to elements in the
subgroup $\mathcal{D}_{n}$. The subgroup $\mathcal{D}_{n}$ in the way it is
defined can naturally be identified with a subgroup of
$\mathop{\mathrm{Aut}}({G_{n,1}})$ and generally of
$\mathop{\mathrm{Aut}}({G_{n,r}})$. This fact, together with results in the
articles cited above, yields the following:

######  Theorem 1.2.

For any $1\leq r\leq n-1$ and any $m\geq 2$,
$\mathop{\mathrm{Out}}({G_{n,r}})$ and $\mathop{\mathrm{Aut}}({G_{n,r}})$
contain an isomorphic copy of
$\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})$.

We note that the article [3] shows that
$\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})$ embeds as a subgroup
of $\mathcal{O}_{n,r}$ but says nothing about an embedding in
$\mathop{\mathrm{Aut}}({G_{n,r}})$. The result above gives a new embedding
into $\mathcal{O}_{n,r}$, specifically into $\mathcal{D}_{n}$, and lifts the
embedding to $\mathop{\mathrm{Aut}}({G_{n,r}})$ by lifting $\mathcal{D}_{n}$.
A quick survey of the literature now demonstrates that
$\mathop{\mathrm{Aut}}({G_{n,r}})$ and $\mathcal{O}_{n,r}$ contain isomorphic
copies of the following groups: finite groups, finitely generated abelian
groups, free groups [11, 15]; free products of finite groups, fundamental
groups of 2-manifolds, graph groups and countable locally finite residually
finite groups [17] to name a few.

We further note that since the order problem is undecidable in
$\mathcal{K}_{n}\cong\mathrm{Inert}_{n}$, we obtain from Theorem 1.2 another
proof of the result in [3] that the order problem is undecidable in the group
$\mathcal{O}_{n,r}$ and $\mathop{\mathrm{Aut}}({G_{n,r}})$ for any $1\leq
r\leq n-1$.

Lastly, we extend a fairly straight-forward result for
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to the groups
$\mathcal{O}_{n,r}$. The homeomorphism $\overleftarrow{\phantom{a}}$, an
involution, of $X_{n}^{\mathbb{Z}}$ which maps a sequence
$(x_{i})_{i\in\mathbb{Z}}$ to the sequence $(y_{i})_{i\in\mathbb{Z}}$ defined
such that $y_{i}=x_{-i}$ induces by conjugation an automorphism
$\overleftarrow{\mathfrak{r}}$ of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$. Since this
automorphism preserves the centre of the group, we have an induced
automorphism of $\mathcal{L}_{n}$. We extend the automorphism
$\overleftarrow{\mathfrak{r}}$ to the group $\mathcal{O}_{n}$ (that is the
extension coincides with $\overleftarrow{\mathfrak{r}}$ on $\mathcal{L}_{n}$).

######  Theorem 1.3.

There is a non-trivial automorphism $\overleftarrow{\mathfrak{r}}$ of order
$2$ of the group $\mathcal{O}_{n}$.

There is no obvious action of $\mathcal{O}_{n}$ on $X_{n}^{\mathbb{Z}}$ by
homeomorphisms, thus the proof of Theorem 1.3 is not as straight-forward as
for $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$. In particular,
the proof outlined above does not go through and we need to do something
different to prove Theorem 1.3. Our proof approach makes use of the
representation of elements of $\mathcal{O}_{n}$ by transducers and the result
in [3] that there is a faithful representation of $\mathcal{O}_{n}$ in the
symmetric group $\mathrm{Sym}(\mathsf{W}_{n}^{\ast})$ of the set
$\mathsf{W}_{n}^{\ast}$. (Here $\mathsf{W}_{n}^{\ast}$ is the set of
equivalence classes of prime words on an alphabet of size $n$ under the
equivalence relation which relates words which are rotations of each other.)
We show that reversing the arrows in a _Moore_ diagram for a transducer for
$\mathcal{O}_{n}$ gives a faithful action of $\mathcal{O}_{n}$ on
$\mathsf{W}_{n}^{\ast}$ by considering the action on circuits. We then give an
algorithm which recovers from the ‘reversed transducer’ a representative in
$\mathcal{O}_{n}$ with the same action on $\mathsf{W}_{n}^{\ast}$. It is of
interest to know whether the map $\overleftarrow{\mathfrak{r}}$ restricts to
an automorphism of $\mathcal{O}_{n,1}$. More generally, one can ask if the
group $\mathcal{O}_{n,1}$ is a characteristic subgroup of $\mathcal{O}_{n}$.
We hope to address these in subsequent articles. Indeed, as a first step, in a
forthcoming article we demonstrate that the group $\mathcal{O}_{n}$ is
isomorphic to the mapping class group of the full shift (see [8, 7, 6, 13] for
instance) over $n$ letters.

The paper is organised as follows. In Section 2 we give the necessary
defintions and background results. Section 3 considers the various extensions
of the homomorphism from $\mathcal{L}_{n}$ to the group $\mathfrak{U}_{n-1,n}$
and develops consequences of these. Section 4 establishes the isomorphism
between the group $\mathcal{K}_{n}$ and the group $\mathrm{Inert}_{n}$. In
this section we also extend the automorphism $\overleftarrow{\mathfrak{r}}$ to
the group $\mathcal{O}_{n}$. In Section 5, where the paper concludes, we
consider a combinatorially defined subgroup $\mathcal{D}_{n}$ of
$\mathcal{K}_{n}$; we show that the index of $\mathcal{D}_{n}$ in
$\mathcal{K}_{n}$ is infinite and demonstrate that various marker
constructions yield elements of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ which reside in
$\mathcal{D}_{n}$. Pulling together results of the literature then yields
various embedding results for the groups $\mathop{\mathrm{Aut}}({G_{n,r}})$
and $\mathop{\mathrm{Out}}({G_{n,r}})$.

## Acknowledgements

The author wishes to acknowledge support from EPSRC research grant
EP/R032866/1, Leverhulme Trust Research Project Grant RPG-2017-159 and the LMS
Early Career Fellowship grant ECF-1920-105.

##  2 Preliminaries

We introduce notation and terminology that we make use of in this work. These
can be divided into two categories: those related to the free monoid over an
alphabet and the Cantor space of singly- and bi-infinite sequences over a
finite alphabet; and those pertaining to transducers.

There is one minor piece of notation which does not fit in the above
categories that is work mentioning. For $i\in\mathbb{N}$, we write
$\mathbb{N}_{i}$ for the set of natural number bigger than or equal to $i$.

###  2.1 Words and Cantor space

Throughout $X_{n}$ will denote the set $\\{0,1,\ldots,n\\}$. Let $X$ be a
finite set, we write $X^{\ast}$ for the set of all finite strings (including
the empty string $\varepsilon$) over the alphabet $X$. Write $X^{+}$ for the
set $X^{\ast}\backslash\\{\varepsilon\\}$. For an element $w\in X$, we write
$|w|$ for the length of $w$. Thus, the empty string is the unique element of
$X^{\ast}$ such that $|\varepsilon|=0$. For elements $x,y\in X^{\ast}$ we
write $xy$ for the concatenation of $x$ and $y$. Give $x\in X^{+}$ and
$k\in\mathbb{N}$, we write $x^{k}$ for the word $w_{1}w_{2}\ldots w_{k}$ where
$w_{i}=x$ for all $1\leq i\leq k$.

Given $k\in\mathbb{N}$ we write $X^{k}$ for the set of all words in $X^{+}$ of
length exactly $k$.

Let $w\in X^{+}$ and write $w=w_{1}w_{2}\ldots w_{r}$ for $w_{i}\in X$, $1\leq
i\leq r$. Then for some $j\in\mathbb{N}$, $1\leq j\leq r$ we say that
$w^{\prime}=w_{j}\ldots w_{r}w_{1}\ldots w_{r}$ is the _$j$ ’th rotation of
$w$_. A word $w^{\prime}$ is called a _rotation_ of $w$ if it is a $j$th
rotation of $w$ for some $1\leq j\leq|w|$. If $j>1$, then $w^{\prime}$ is
called a _non-trivial rotation of_ $w$. The word $w$ is said to be a prime
word if $w$ is not equal to a non-trivial rotation of itself. Alternatively,
$w$ is a prime word if there is no word $\gamma\in X^{+}$ such that
$w=\gamma^{|w|/|\gamma|}$.

The relation on $X^{\ast}$ which relates two words if one is a rotation of the
other is an equivalence relation. We write $\sim_{{\mathmbox{rot}}}$ for this
equivalence relation. It will be clear from the context which alphabet is
meant.

We write $W_{n}^{\ast}$ for the set of all prime words over the alphabet
$X_{n}$. For $k\in\mathbb{N}$, $W_{n}^{k}$ will denote the set of all prime
words of length $k$ over the alphabet. We shall write $\mathsf{W}_{n}^{\ast}$
for the set of equivalence classes $W_{n}^{\ast}/\sim_{{\mathmbox{rot}}}$;
$\mathsf{W}_{n}^{+}$ for the set of equivalence classes
$W_{n}^{+}/\sim_{{\mathmbox{rot}}}$; $\mathsf{W}_{n}^{k}$ for the set of
equivalence classes $W_{n}^{k}/\sim_{{\mathmbox{rot}}}$.

For $x,y\in X^{\ast}$ we write, $x\leq y$ if $x$ is a prefix of $y$, in this
case we write $y-x$ for the word $z\in X^{\ast}$ such that $xz=y$. If
$x\not\leq y$ and $y\not\leq x$, then we say that $x$ and $y$ are
_incomparable_ and write $x\perp y$ to denote this.

An _antichain_ is a subset $W$ of $X^{\ast}$ consisting of pairwise
incomparable elements. That is for $u,v\in W$, $u\not\perp v$ if and only if
$u=v$. An antichain $W$ is called complete if every element of $X^{*}$ of long
enough length has a prefix in $W$.

A _bi-infinite sequence_ over the alphabet $X$ is a map $x:\mathbb{Z}\to X$
and we write such a sequence as $\ldots x_{-2}x_{-1}x_{0}x_{1}x_{2}\ldots$
where $x_{i}=x(i)$ for $i\in\mathbb{Z}$. In a similar way a _(positive) singly
infinite sequence_ is a map $x:\mathbb{N}\to X$ and, analogously, we write
such a sequence as $x_{0}x_{1}\ldots$. A _(negative)) singly infinite
sequence_ is a map $:x:-\mathbb{N}\to X$ and is denoted $\ldots
x_{-2}x_{-1}x_{0}$. We write $X^{\mathbb{N}},X^{-N}$ and $X^{\mathbb{Z}}$
respectively for the sets of positive singly infinite sequences, negative
singly infinite sequences and bi-infinite sequences.

For $x\in(X^{\mathbb{N}}\sqcup X^{-\mathbb{N}}\sqcup X^{\mathbb{Z}}\sqcup
X^{\ast})$ and $i\leq j\in\mathbb{Z}$ where $j\leq|x|$ and $i$ is bigger than
or equal to the smallest index of $x$ ($0$ if $x\in X^{\mathbb{N}}\sqcup
X^{\ast}$ and $-\infty$ otherwise), we write $x_{[i,j]}$ for the sequence
$x_{i}x_{i+1}\ldots x_{j}$.

We may concatenate, in a natural way, a string with a positive infinite
sequence or a negative infinite sequence with a positive infinite sequence.
Given an element $\gamma\in X^{+}$ and a positive infinite sequence $x$ with
prefix $\gamma$, we write $x-\gamma$ for the positive infinite sequence $y$
such that $\gamma y=x$.

Let $\overleftarrow{\phantom{a}}:X^{\ast}\to X^{\ast}$ be defined as follows:
$\overleftarrow{\varepsilon}=\varepsilon$, and for $w\in X^{+}$ with
$w=w_{1}\ldots w_{r}$, $w_{i}\in X$ for all $1\leq i\leq r$,
$\overleftarrow{w}=w_{r}w_{r-1}\ldots w_{1}$. We also write
$\overleftarrow{\phantom{a}}$ for the map from $X^{\mathbb{N}}\sqcup
X^{-\mathbb{N}}\to X^{\mathbb{N}}\sqcup X^{-\mathbb{N}}$ defined by
$\overleftarrow{x_{0}x_{1}\ldots}=\ldots x_{2}x_{1}x_{0}$ and
$\overleftarrow{\ldots x_{2}x_{1}x_{0}}=x_{0}x_{1}\ldots$ . In particular for
any prefix $w$ of $x_{0}x_{1}\ldots$. $\overleftarrow{w}$ is a suffix of
$\overleftarrow{x_{0}x_{1}\ldots}$ and vice versa. We note that
$\overleftarrow{\phantom{a}}$ is an involution.

Taking the product topology on each of the sets $X_{n}^{\omega}$,
$X_{n}^{-\mathbb{N}}$ and $X_{n}^{\mathbb{Z}}$, makes each homeomorphic to
Cantor space. We introduce some notation for basic open sets in these spaces.
Let $\gamma\in X_{n}^{*}$ be a word. We denote by $U^{+}_{\gamma}$ the subset
of $X_{n}^{\omega}$ consisting of all elements with prefix $\gamma$;
$U^{-1}_{\gamma}$ the subset of $X_{n}^{-\mathbb{N}}$ consisting of all
elements with suffix $\gamma$; we use the notation $U^{0}_{\gamma}$ for the
subset of all elements of $X_{n}^{\mathbb{Z}}$ such that $x_{0}\ldots
x_{|\gamma|-1}=\gamma$.

The shift map $\sigma_{n}:X_{n}^{\mathbb{Z}}\sqcup X_{n}^{-\mathbb{N}}\to
X_{n}^{\mathbb{Z}}\sqcup X_{n}^{-\mathbb{N}}$ is the map which sends a
sequence $x\in X_{n}^{\mathbb{Z}}\sqcup X_{n}^{-\mathbb{N}}$ to the sequence
$y\in X_{n}^{\mathbb{Z}}\sqcup X_{n}^{-\mathbb{N}}$ defined by
$y_{i}=x_{i-1}$, for all $i$ for which $x_{i}$ is defined. We retain the
symbol $\sigma_{n}$ for the restrictions to the subspaces $X_{n}^{\mathbb{Z}}$
and $X_{n}^{-\mathbb{N}}$. We note that $\sigma_{n}X_{n}^{-\mathbb{N}}\to
X_{n}^{-\mathbb{N}}$ is a continuous surjection, and
$\sigma_{n}:X_{n}^{\mathbb{Z}}\to X_{n}^{\mathbb{Z}}$ is a homeomorphism.

Let $F(X_{n},m)$ denote the set of functions from $X_{n}^{m}$ to $X_{n}$.
Then, for all $m,r>0$, and all $f\in F(X_{n},m)$, we define a map
$f_{r}:X_{n}^{m+r-1}\to X_{n}^{r}$ as follows.

> Let $x=x_{-m-r+2}\ldots x_{0}$. For $-r+1\leq i\leq 0$, set
> $y_{i}=(x_{i-m+1}x_{i-m+2}\ldots x_{i})f$. Then $xf_{r}=y$, where
> $y=y_{-r+1}\ldots y_{0}$.

Thus, as in the paper [5], we have a “window” of length $m$ which slides along
the sequence $x$ and at the $i$’th step we apply the map $f$ to the symbols
visible in the window. We think of the map $f$ as acting on the rightmost
letter in the viewing window according to the $m-1$ digits of history. This
procedure can be extended to define a map $f_{\infty}:X_{n}^{\mathbb{Z}}\to
X_{n}^{\mathbb{Z}}$, by setting $xf_{\infty}=y$ where $y_{i}=(x_{i-m+1}\ldots
x_{i})f$ for all $i\in\mathbb{Z}$; and similarly for $X_{n}^{-\mathbb{N}}$.

A function $f\in F(X_{n},m)$ is called _right permutive_ if, for distinct
$x,y\in X_{n}$ and any fixed block $a\in X_{n}^{m-1}$, we have
$(ax)f\neq(ay)f$. Analogously, a function $f\in F(X_{n},m)$ is called _left
permutive_ if the map from $X_{n}$ to itself given by $x\mapsto(xa)f$ is a
permutation for all $a\in X_{n}^{m-1}$. If $f$ is not right permutive, then
the induced map $f_{\infty}$ from $X_{n}^{-\mathbb{N}}$ to itself is not
injective. Moreover, it not always the case that a right permutive map $f\in
F(X_{n},m)$ induces a bijective map $f_{\infty}:X_{n}^{-\mathbb{N}}\to
X_{n}^{-\mathbb{N}}$, however, a right permutive map always induces a
surjective map from $X_{n}^{-\mathbb{N}}$ to itself.

######  Remark 2.1.

Observe that, if $f\in F(X_{n},m)$ and $k\geq 1$, then the map $g\in
F(X_{n},m+k)$ given by $(x_{-m-k+1}\ldots x_{0})g=(x_{-m+1}\ldots x_{0})f$,
satisfies $g_{\infty}=f_{\infty}$.

The following result is due to Curtis, Hedlund and Lyndon [15, Theorem 3.1]:

######  Theorem 2.2.

Let $f\in F(X_{n},m)$. Then $f_{\infty}$ is continuous and commutes with the
shift map on $X_{n}^{\mathbb{Z}}$.

A continuous function from $X_{n}^{\mathbb{Z}}$ to itself which commutes with
the shift map is called an _endomorphism_ of the shift dynamical system
$(X_{n}^{\mathbb{Z}},\sigma_{n})$. If the function is invertible, since
$X_{n}^{\mathbb{Z}}$ is compact and Hausdorff, its inverse is continuous: it
is an _automorphism_ of the shift system. The sets of endomorphisms and of
automorphisms are denoted by
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$ and
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ respectively. Under
composition, the first is a monoid, and the second a group.

Analogously, a continuous function from $X_{n}^{-\mathbb{N}}$ to itself which
commutes with the shift map on this space is an _endomorphism of the one-sided
shift_ $(X_{n}^{-\mathbb{N}},\sigma_{n})$; if it is invertible, it is an
_automorphism_ of this shift system. The sets of such maps are denoted by
$\mathop{\mathrm{End}}\nolimits(X_{n}^{-\mathbb{N}},\sigma_{n})$ and
$\mathop{\mathrm{Aut}}({X_{n}^{-\mathbb{N}},\sigma_{n}})$; again the first is
a monoid and the second a group.

Note that
$\sigma_{n}\in\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, whereas
$\sigma_{n}\in\mathop{\mathrm{End}}\nolimits(X_{n}^{-\mathbb{N}},\sigma_{n})\setminus\mathop{\mathrm{Aut}}({X_{n}^{-\mathbb{N}},\sigma_{n}})$.

Define

$\displaystyle F_{\infty}(X_{n})$ $\displaystyle=$
$\displaystyle\bigcup_{m\geq 0}\\{f_{\infty}:f\in F(X_{n},m)\\},$
$\displaystyle RF_{\infty}(X_{n})$ $\displaystyle=$
$\displaystyle\bigcup_{m\geq 0}\\{f_{\infty}:f\in F(X_{n},m),f\mbox{ is right
permutive}\\}.$

Theorem 2.2 shows that
$F_{\infty}(X_{n})\subseteq\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}})$.
In fact $F_{\infty}(X_{n})$ and $RF_{\infty}$ are submonoids of
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}})$. Note that $\sigma_{n}\in
F_{\infty}(X_{n})$, but $\sigma_{n}^{-1}$ is not an element of
$F_{\infty}(X_{n})$. Now, [15, Theorem 3.4] shows:

######  Theorem 2.3.

$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})=\\{\sigma_{n}^{i}\phi\mid
i\in\mathbb{Z},\phi\in F_{\infty}(X_{n})\\}$.

The following result is a corollary:

######  Theorem 2.4.

$RF_{\infty}$ is a submonoid of
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$ and
$\mathop{\mathrm{Aut}}({X_{n}^{-\mathbb{N}},\sigma_{n}})$ is the largest
inverse closed subset of $RF_{\infty}(X_{n})$.

###  2.2 Transducers

In this section we state a result of [3] which shows how the elements of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ can be described by a
pair consisting of a possibly _asynchronous_ transducer, and combinatorial
data called an _annotation_. We begin with a general definition of automata
and transducers.

###  2.3 Automata and transducers

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

  1. 1.

$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. 2.

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

  3. 3.

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

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 inputs to $A$ form a string in $X_{n}^{\mathbb{N}}$;
after reading a symbol, the read head moves one place to the right before the
next operation.

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 with initial state $q$
after successively reading the symbols in $w$. 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 labelled directed graph, whose vertex
set is $Q_{A}$; there is a directed edge labelled by $a\in X_{a}$ from $q$ to
$r$ if $\pi_{A}(a,q)=r$.

A _circuit_ in the automaton $A$ is therefore a word $w\in X_{n}^{*}$ and a
state $q\in Q_{A}$ such that $\pi_{T}(w,q)=q$. We say that $w$ is a _circuit
based at $q$_. If $|w|=1$, we say that $w$ is a _loop based at $q$_ and $q$ is
called a _$w$ loop state_. A circuit $w$ based at a state $q$ is called
_basic_ if, writing $w=w_{1}\ldots w_{|w|}$, for all $1\leq i<j<|w|$,
$\pi_{T}(w_{1}\ldots w_{i},q)\neq\pi_{T}(w_{1}\ldots w_{j},q)$.

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

  1. 1.

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

  2. 2.

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

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)$. An _initial
transducer_ $T_{q}$ is simply a transducer which starts in state $q$.

We note that the transducers defined above are _deterministic_. In other words
the transition function is in fact a function. In Subsection 4.2 we consider
general _non-deterministic transducers_ in which there might be multiple ways
of reading a word from a state. As the more general definition is only
required in that subsection we state it there.

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

A transducer $T$ can also be represented as an edge-labelled 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.

For example, Figure 1 describes a 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}$

A transducer $T$ is said to be _synchronous_ if $|\lambda_{T}(a,q)|=1$ for all
$a\in X_{T}$, $q\in Q_{T}$; in other words, when it reads a symbol, it writes
a single symbol. It is _asynchronous_ otherwise. Thus, an asynchronous
transducer may write several symbols, or none at all, at a given step. Note
that this usage of the word differs from that of Grigorchuk _et al._ [14], for
whom “asynchronous” includes “synchronous”. The transducer of Figure 1 is
synchronous.

We can regard an automaton, or a transducer, as acting on an infinite string
in $X_{n}^{\omega}$, 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)).$

Throughout this paper, we will (as in [14]) make the following assumption:

##### Assumption

A transducer $T$ has the property that, when it reads an infinite input string
starting from any state, it writes an infinite output string.

The property above is equivalent to the property that any circuit in the
underlying automaton has non-empty concatenated output.

From the assumption, it follows that the transducer writes an infinite output
string on reading any infinite input string from any state. Thus $T_{q}$
induces a map $w\mapsto\lambda_{T}(w,q)$ from $X_{n}^{\omega}$ 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 $\mathrm{Image}{(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 [14].) 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}^{\omega}$.

A transducer is said to be _weakly minimal_ if no two states are
$\omega$-equivalent. For a synchronous 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.

For a state $q$ of $T$ and a word $w\in X_{n}^{*}$, we let $\Lambda(w,q)$ be
the greatest common prefix of the set $\\{\lambda(wx,q):x\in
X_{n}^{\omega}\\}$. The state $q$ is called a _state of incomplete response_
if $\Lambda(\varepsilon,q)\neq\varepsilon$; the length
$|\Lambda(\varepsilon,q)|$ of the string $\Lambda(\varepsilon,q)$ is the
_extent of incomplete response_ of the state $q$. Note that for a state $q\in
Q_{T}$, if the initial transducer $T_{q}$ induces a map from $X_{n}^{\omega}$
to itself with image size at least $2$, then
$|\Lambda(\varepsilon,q)|<\infty$.

Let $T$ be a transducer and $q\in Q_{T}$ a state. Suppose $T_{q}$ has image
size exactly one. By definition the number of states of $T_{q}$ is finite,
therefore there is a state $p\in Q_{p}$, accessible from $q$ and a word
$\Gamma\in X_{n}^{+}$ such that $\pi_{T}(\Gamma,p)=p$. Let
$x=\lambda_{T}(\Gamma,p)\in X_{n}^{+}$ and let
$Z_{x}=(X_{n},\\{x\\},\pi_{Z_{x}},\lambda_{Z_{x}})$ be the transducer such
that $\lambda_{Z_{x}}(i,x)=x$ for all $i\in X_{n}$. Then $T_{q}$, is
$\omega$-equivalent to a transducer $T^{\prime}_{q^{\prime}}$ which contains
$Z_{x}$ as a subtransducer and satisfies the following condition: there is a
$k\in\mathbb{N}$ so that, for any word $y\in X_{n}^{*}$,
$\pi_{T^{\prime}}(y,q^{\prime})=x$.

We say that an initial transducer $T_{q}$ is _minimal_ if it is weakly
minimal, has no states of incomplete response and every state is accessible
from the initial state $q$.

A non-initial transducer $T$ is called minimal if for any state $q\in Q_{T}$
the initial transducer $T_{q}$ is minimal. Therefore a non-initial transducer
$T$ is minimal if it is weakly minimal, has no states of incomplete response
and is strongly connected as a directed graph.

Observe that the transducer $Z_{x}$, for any $x\in X_{n}^{+}$, is not minimal
as its only state is, by definition, a state of incomplete response. However,
it will be useful when stating some results later on to have a notion of
minimality for the single state transducers $Z_{x}$ considered as initial and
non-initial transducers. We use the word minimal for this new meaning of
minimality appealing to the context to clarify any confusion. The definition
below, which perhaps appears somewhat contrived, is a consequence of this.

Let $x=x_{1}x_{2}\ldots x_{r}\in X_{n}^{*}$ be a word. The transducer $Z_{x}$
is called _minimal as an initial transducer_ if $x$ is a prime word; $Z_{x}$
is called _minimal as a non-initial transducer_ if $Z_{x}$ is minimal as an
initial transducer and $x$ is the minimal element, with respect to the
lexicographic ordering, of the set $\\{x_{i}\ldots x_{r}x_{1}\ldots
x_{i-1}|1\leq i\leq r\\}$. Note that if $|x|=1$ then $Z_{x}$ is minimal as an
initial transduce if and only if it is minimal as a non-initial transducer. In
most applications, we consider the transducers $Z_{x}$ as non-initial
transducers and in this case we will omit the phrase ‘as a non-initial
transducer’.

Two (weakly) 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 (weakly)
minimal initial transducers $T_{p}$ and $U_{q}$ are said to be $\omega$-equal
if there is a bijection $f:Q_{T}\to Q_{U}$, such that $(p)f=q$ and for any
$t\in Q_{T}$, $T_{t}$ is $\omega$-equivalent to $U_{(t)f}$. We shall use the
symbol ‘$=$’ to represent $\omega$-equality of initial and non-initial
transducers. Two non-initial transducers are said to be $\omega$-equivalent if
they have $\omega$-equal minimal representatives.

In the class of synchronous transducers, the $\omega$-equivalence class of any
transducer has a unique weakly minimal representative. Grigorchuk et al. [14]
prove that the $\omega$-equivalence class of an initialised transducer $T_{q}$
has a unique minimal representative, if one permits infinite outputs from
finite inputs, and give an algorithm for computing this representative. The
first step of this algorithm is to create a new transducer $T_{q_{-1}}$ which
is $\omega$-equivalent to $T_{q}$ and has no states of incomplete response. As
we do not allow our transducers to write infinite strings on finite inputs, we
impose an additional condition: we apply the process for removing incomplete
response only in instances where all states accessible from the initial one
have finite extent of incomplete response.

######  Propostion 2.5.

Let $A_{q_{0}}=(X_{n},Q_{A},\pi_{A},\lambda_{A})$ be a finite initial
transducer such that $|\Lambda(\varepsilon,q)|<\infty$ for all $q\in Q_{A}$.
Set $Q^{\prime}_{A}:=Q\cup\\{q_{-1}\\}$, where $q_{-1}$ is a symbol not in
$Q_{A}$. Define: rCl π’_A(x,q_-1) &= π_A(x,q_0),
π’_A(x,q) = π_A(x,q),
λ_A(x, q_-1) = Λ(x,q_0),
λ’_A(x,q) = Λ(x, q) - Λ(ε,q), for all $x\in X_{n}$ and $q\in Q_{A}$.

Then, the transducer
$A^{\prime}=(X_{n},Q^{\prime}_{A},\pi^{\prime}_{A},\lambda^{\prime}_{A})$ with
the initial state $q_{-1}$ is a transducer which is $\omega$-equivalent to the
transducer $A_{q_{0}}$ and has no states of incomplete response.

In addition, for every $w\in X_{n}^{\ast}$, the following inequality holds:

$\lambda^{\prime}_{A}(w,q_{-1})=\Lambda(w,q_{0}).$ (1)

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 and not
$\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 S_{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$.

We say that an initial transducer $T_{q}$ is _invertible_ if there is an
initial transducer $U_{p}$ such that $T_{q}*U_{p}$ and $U_{p}*T_{q}$ each
induce the identity map on $X_{n}^{\omega}$. We call $U_{p}$ an _inverse_ of
$T_{q}$. When this occurs we will denote $U_{p}$ as $T_{q}^{-1}$.

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}:=\pi_{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}$.

In this article, we will come across synchronous transducers which are not
invertible in the automata theoretic sense but which nevertheless induce self-
homeomorphims of the space $X_{n}^{\mathbb{Z}}$ and so are invertible in a
different sense.

###  2.4 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,
if the automaton reads the word $w$ of length $k$, the final state depends
only on $w$ and not on the initial state. (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 [21, 1]. 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 set of states forming the image of the map $\mathfrak{s}_{k}$.
The core of $A$ is an automaton in its own right, and is also synchronizing at
level $k$. We denote this automaton by $\mathrm{Core}(A)$. We say that an
automaton or transducer is _core_ if it is equal to its core.

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

######  Propostion 2.6.

Let $T_{q}$, $U_{p}$ be synchronous initial transducers which (as automata)
are synchronizing at levels $j$, $k$ respectively, Then $T*U$ is synchronizing
at level at most $j+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 synchronous and 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.

######  Notation 2.7.

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

###  2.5 Groups and monoids of Transducers

We define several monoids and groups whose elements consists of
$\omega$-equivalence classes of transducers which appear first in the papers
[4, 3]. In practise, as each $\omega$-equivalence class contains a unique
minimal element as exposited above, we represent the elements of these monoids
will be minimal transducers. These monoids and groups play a central role in
what follows

####  2.5.1 The monoid $\widetilde{\mathcal{P}}_{n}$

Let $T$ be a transducer which is synchronous and which (regarded as an
automaton) is synchronizing at level $k$, then the core of $T$ (similarly
denoted $\mathrm{Core}(T)$) induces a continuous map
$f_{T}:X_{n}^{\mathbb{Z}}\to X_{n}^{\mathbb{Z}}$. The function
$f_{T}:X_{n}^{\mathbb{Z}}\to X_{n}^{\mathbb{Z}}$ induced by a strongly
synchronizing transducer $T$ is defined as follows.

Let $T$ be a transducer which is core, synchronous and which is synchronizing
at level $k$. The map $f_{T}$ maps an element $x\in X_{n}^{\mathbb{Z}}$ to the
sequence $y$ defined by $y_{i}=\lambda_{T}(x_{i},q_{x_{i-k}x_{i-k+1}\ldots
x_{i-1}})$. We observe that for an element $x\in X_{n}^{\mathbb{Z}}$, and
$i\in\mathbb{Z}$, if $(x)f_{T}=y$, then, by definition,
$y_{i}y_{i+1}\ldots=\lambda_{T}(x_{i}x_{i+1}\ldots,q_{x_{i-k}x_{i-k+1}\ldots
x_{i-1}})$.

Clearly, if $T$ is synchronizing at level $k$, then it is synchronizing at
level $l$ for all $l\geq k$; but the map $f_{T}$ is independent of the level
chosen to define it.

Now strongly synchronizing transducers may induce endomorphisms of the shift
[5]:

######  Propostion 2.8.

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

The transducer in Figure 1 induces the shift map on $X_{n}^{\mathbb{Z}}$. More
generally, let
$\mathfrak{S}_{n}=(X_{n},Q_{\mathfrak{S}_{n}},\pi_{\mathfrak{S}_{n}},\lambda_{\mathfrak{S}_{n}})$
be the transducer defined as follows. Let
$Q_{\mathfrak{S}_{n}}:=\\{0,1,2,\ldots,n-1\\}$, and let
$\pi_{\mathfrak{S}_{n}}:X_{n}\times Q_{\mathfrak{S}_{n}}\to
Q_{\mathfrak{S}_{n}}$ and $\lambda_{\mathfrak{S}_{n}}:X_{n}\times
Q_{\mathfrak{S}_{n}}\to X_{n}$ be defined by $\pi_{\mathfrak{S}_{n}}(x,i)=x$
and $\lambda_{\mathfrak{S}_{n}}(x,i)=i$ for all $x\in X_{n}$ $i\in
Q_{\sigma_{n}}$. Then $f_{\mathfrak{S}_{n}}=\sigma_{n}$.

In [4], the authors show that the set $\widetilde{\mathcal{P}}_{n}$ of weakly
minimal finite 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 weakly
minimal and synchronous representative. Let $\mathcal{P}_{n}$ be the subset of
$\widetilde{\mathcal{P}}_{n}$ consisting of transducers which induce
automorphisms of the shift. (Note that these may not be minimal.) Clearly
$\mathfrak{S}_{n}\in\mathcal{P}_{n}$.

The following result is proved in [5].

######  Corollary 2.9.

The monoid $F_{\infty}(X_{n})$ is isomorphic to $\widetilde{\mathcal{P}}_{n}$.

####  2.5.2 The monoids $\mathcal{M}_{n}$, $\widetilde{\mathcal{O}_{n}}$ and
$\widetilde{\mathcal{L}_{n}}$

Let $\mathcal{M}_{n}$ be the set of all non-initial, minimal, strongly
synchronizing and core transducers. Recall that for $x\in X_{n}^{+}$,
$Z_{x}=(X_{n},\\{x\\},\pi_{Z_{x}},\lambda_{Z_{x}})$ is the transducer such
that $\lambda_{Z_{x}}(i,x)=x$ for all $i\in X_{n}$. Moreover
$Z_{x}\in\mathcal{M}_{n}$ for a prime words $x=x_{0}x_{1}\ldots x_{r}\in
X_{n}^{+}$ if and only if $x$ is the minimal, with respect to the
lexicographic ordering, element of the set $\\{x_{i}\ldots x_{r}x_{1}\ldots
x_{i-1}|1\leq i\leq r\\}$. If $T\in\mathcal{M}_{n}$ is a strongly
synchronizing and core transducer, such that some state (and so all states by
connectivity) has infinite extent of incomplete response, then $T=Z_{x}$ for
some minimal non-initial transducer $Z_{x}$. Let $\widetilde{\mathcal{O}_{n}}$
be the subset of $\mathcal{M}_{n}$ consisting of all transducers $T$
satisfying the following conditions:

  1. S1

for any state $t\in Q_{T}$, the initial transducer $T_{t}$ induces a injective
map $h_{t}:X_{n}^{\omega}\to X_{n}^{\omega}$ and,

  2. S2

for any state $t\in Q_{T}$ the map $h_{t}$ has clopen image which we denote by
$\mathrm{Image}{(t)}$.

Note that an element of $\mathcal{M}_{n}$ with more than one state has no
states of incomplete response. The single state identity transducer is an
element of $\mathcal{M}_{n}$ and we denote it by $\mathbbm{1}$.

Following [3] we define a binary operation on the set $\mathcal{M}_{n}$ as
follows. For two transducers $T,U\in\mathcal{M}_{n}$, the product transducer
$T\ast U$ is strongly synchronizing. Let $TU$ be the transducer obtained from
$\mathrm{Core}(T\ast U)$ as follows. Fix a state $(t,u)$ of
$\mathrm{Core}(T\ast U)$. Then $TU$ is the core of the minimal representative
of the initial transducer $\mathrm{Core}(T\ast U)_{(t,u)}$. That is, if any
state (and so all states by connectivity) of $\mathrm{Core}(T\ast U)$ has
finite extent of incomplete response we remove the states of incomplete
response from $\mathrm{Core}(T\ast U)_{(t,u)}$ to get a new transducer initial
$(TU)^{\prime}_{q_{-1}}$ which is still strongly synchronizing and has all
states accessible from the initial state. Then we identify the
$\omega$-equivalent states of $(TU)^{\prime}_{q_{-1}}$ to get a minimal,
strongly synchronizing initial transducer $(TU)_{p}$. The transducer $TU$ is
the core of $(TU)_{p}$. Otherwise, for any state $(t,u)\in\mathrm{Core}(T,U)$,
$\mathrm{Core}(T,U)_{(t,u)}$ is $\omega$-equivalent to a transducer of the
form $Z_{x}$ for some prime word $x=x_{1}\ldots x_{r}\in X_{n}^{+}$ and we set
$TU=Z_{\overline{x}}$ where $\overline{x}$ is the minimal element, with
respect to the lexicographic ordering, of the set $\\{x_{i}\ldots
x_{r}x_{1}\ldots_{i-1}|1\leq i\leq r\\}$.

It is a result of [3] that $\mathcal{M}_{n}$ together with the binary
operation $\mathcal{M}_{n}\times\mathcal{M}_{n}\to\mathcal{M}_{n}$ given by
$(T,U)\mapsto TU$ is a monoid. (The single state transducer $\mathbbm{1}$
which induces the identity permutation on $X_{n}$ is the identity element.)

A consequence of a result in [4] is that an element $T\in\mathcal{M}_{n}$ is
an element of $\widetilde{\mathcal{O}_{n}}$ if and only if for any state $q\in
Q_{T}$ there is a minimal, initial transducer $U_{p}$ such that the minimal
representative of the product $(T\ast U)_{(p,q)}$ is strongly synchronizing
and has trivial core. If the transducer $U_{p}$ is strongly synchronizing as
well then $\mathrm{Core}(U_{p})\in\widetilde{\mathcal{O}_{n}}$ and satisfies
$T\mathrm{Core}(U_{p})=\mathrm{Core}(U_{p})T=\mathbbm{1}$.

The group $\mathcal{O}_{n}$ is the largest inverse closed subset of
$\widetilde{\mathcal{O}_{n}}$.

We give below a procedure for constructing the inverse of an element
$T\in\widetilde{\mathcal{O}_{n}}$.

######  Construction 2.10.

Let $T\in\mathcal{O}_{n}$. For $q\in Q_{T}$ define a map $L_{q}:X_{n}^{+}\to
X_{n}^{*}$ by setting $(w)L_{q}$ to be the greatest common prefix of the set
$(U^{+}_{w})h_{q}^{{}_{1}}$. Set $Q_{T^{\prime}}$ to be the set of pairs
$(w,q)$ where $w\in X_{n}^{*}$, $q\in Q_{T}$,
$U^{+}_{w}\subset\mathrm{Image}{(q)}$ and $(w)L_{q}=\varepsilon$. Define maps
$\pi_{T^{\prime}}:X_{n}\times Q_{T^{\prime}}\to Q_{T^{\prime}}$ and
$\lambda_{T^{\prime}}:X_{n}\times Q_{T^{\prime}}\to X_{n}^{*}$ as follow:
$\pi_{T^{\prime}}(a,(w,q))=wa-\lambda_{T}((wa)L_{q},q)$ and
$\lambda_{T^{\prime}}(a,(w,q))=(wa)L_{q}$. Let $T^{\prime}=\langle
X_{n},Q_{T^{\prime}},\pi_{T^{\prime}},\lambda_{T^{\prime}}\rangle$. It is
shown in [4] that $T^{\prime}$ is a finite transducer and, setting $U$ to be
the minimal representative of $T^{\prime}$, $UT=TU=\mathbbm{1}$.

Let $\widetilde{\mathcal{L}_{n}}$ be those elements $T\in\mathcal{M}_{n}$
which satisfy the following additional constraint:

  1. SL3

for all strings $a\in X_{n}^{\ast}$ and any state $q\in Q_{T}$ such that
$\pi_{T}(a,q)=q$, $|\lambda_{T}(a,q)|=|a|$.

The set $\widetilde{\mathcal{L}_{n}}$ is a submonoid of $\mathcal{M}_{n}$ [4].
Set $\mathcal{L}_{n}:=\mathcal{O}_{n}\cap\widetilde{\mathcal{L}_{n}}$, the
largest inverse closed subset of $\widetilde{\mathcal{L}_{n}}$.

For each $1\leq r\leq n-1$ the group $\mathcal{O}_{n}$ has a subgroup
$\mathcal{O}_{n,r}$ where $\mathcal{O}_{n,n-1}=\mathcal{O}_{n,n}$; we define
$\mathcal{L}_{n,r}:=\mathcal{O}_{n,r}\cap\mathcal{L}_{n}$. The following
theorem is from [4].

######  Theorem 2.11.

For $1\leq r\leq n-1$,
$\mathcal{O}_{n,r}\cong\mathop{\mathrm{Out}}({G_{n,r}})$.

In [3] it is shown that any element of
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$ can be
represented by a pair $(T,\alpha)$ where $T\in\widetilde{\mathcal{L}_{n}}$ and
$\alpha$ is an _annotation_ of $T$. We give a brief exposition of this result.

######  Definition 2.12.

Let $L\in\widetilde{\mathcal{L}_{n}}$. An _annotation_ of $L$ is a map
$\alpha:Q_{L}\to\mathbb{Z}$ which obeys the following rule: for any state
$q\in Q_{L}$ and any word $\Gamma\in X_{n}^{*}$

$(\pi_{L}(\Gamma,q))\alpha=(q)\alpha+|\lambda_{L}(\Gamma,q)|-|\Gamma|.$ (2)

######  Notation 2.13.

Let $T\in\widetilde{\mathcal{L}_{n}}$ and suppose that $T$ admits an
annotation $\alpha$ which assigns $0$ to every state of $T$. Then we call
$\alpha$ the _zero annotation_ and denote it by $\bm{0}$.

We are now in a position to define an action of $\widetilde{\mathcal{L}_{n}}$
on $X_{n}^{\mathbb{Z}}$.

Let $L\in\widetilde{\mathcal{L}_{n}}$, let $\alpha$ be an annotation of $L$
and let $k\in\mathbb{N}$ be the synchronizing level of $L$. Let
$(L,\alpha):X_{n}^{\mathbb{Z}}\to X_{n}^{\mathbb{Z}}$ be defined as follows:
for $x\in X_{n}^{\mathbb{Z}}$ and $i\in\mathbb{Z}$ let $q_{j}$, $1\leq
j\leq|L|$, be the state of $L$ forced by ${x_{i-k}\ldots x_{i-1}}$. Set
$r:=(q_{j})\alpha$ and $w:=\lambda_{L}(x_{i},q_{j})$. Let $y\in
X_{n}^{\mathbb{Z}}$ be defined by ${y_{i+r}y_{i+r+1}\ldots y_{i+r+|w|}}:=w$.
Set $(x)(L,\alpha):=y$.

The following results are from [3].

######  Propostion 2.14.

Let $L\in\widetilde{\mathcal{L}_{n}}$, and let $\alpha$ be an annotation of
$L$. Then $(L,\alpha)$ is an element of
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$.

######  Corollary 2.15.

Let $L\in\widetilde{\mathcal{L}_{n}}$, $i\in\mathbb{Z}$ and $\alpha$ and
$\beta$ be any annotations of $L$, then there is an $i\in\mathbb{Z}$ such that
$(L,\alpha)=\sigma_{n}^{i}(L,\beta)$. In particular $\beta=\alpha+i$.

Let $L,M\in\widetilde{\mathcal{L}_{n}}$, $\alpha$ an annotation of $L$ and
$\beta$ an annotation of $M$. Let $(LM)$ be the core of the transducer product
of $L$ and $M$ with incomplete response removed, and let $LM$ be the product
in $\widetilde{\mathcal{L}_{n}}$ of $L$ and $M$. We note that the states of
$(LM)$ are in bijective correspondence with the states of $L\ast M$ and the
states of $LM$ are $\omega$-equivalence classes of states of $(LM)$. Define a
map from $\overline{\alpha+\beta}:Q_{LM}\to\mathbb{Z}$ as follows. Let $q\in
Q_{LM}$ and let $(s,t)\in Q_{L}\times Q_{M}$ be the state of $(LM)$ such that
$(LM)_{(s,t)}$ is $\omega$-equivalent to $LM_{q}$. Then we set
$(q)\overline{\alpha+\beta}=(s)\alpha+(t)\beta+|\Lambda(\epsilon,(s,t))|$
where $|\Lambda(\epsilon,(s,t))|$ is the extent of incomplete response of
$(s,t)$ as a state of $L\ast M$. It is shown in [3] that
$\overline{\alpha+\beta}$ is an annotation of $LM$.

Set $\widetilde{\mathcal{ASL}_{n}}$ to be the set of pairs $(L,\alpha)$ for
$L\in\widetilde{\mathcal{L}_{n}}$ and $\alpha$ an annotation of $L$. Let
$\mathcal{AL}_{n}$ be the subset of $\widetilde{\mathcal{ASL}_{n}}$ consisting
of elements $(L,\alpha)$ such that $L\in\mathcal{L}_{n}$.The following result
is from [3]

######  Theorem 2.16.

The set $\widetilde{\mathcal{ASL}_{n}}$ with the binary operation mapping
$(L,\alpha)(M,\beta)\to(LM,\overline{\alpha+\beta})$ is a monoid isomorphic to
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$. Moreover, the
subset $\mathcal{AL}_{n}$ of $\widetilde{\mathcal{ASL}_{n}}$ is a subgroup
isomorphic to $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$.

In this work we alternate between the description of elements of
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$ given in
Section 2.1 and the description as pairs of consisting of an element $L$ of
$\widetilde{\mathcal{L}_{n}}$ and an annotation $\alpha$ of $L$.

The paper [3] gives a faithful representation of the monoid $\mathcal{M}_{n}$
in the full transformation monoid
$\mathop{\mathrm{Tr}}(\mathsf{W}_{n}^{\ast})$. We define this representation
below noting that its restriction to the group $\mathcal{L}_{n}$ yields the so
called _periodic orbit_ of [10].

Let $[\gamma]_{\sim_{{\mathmbox{rot}}}}\in\mathsf{W}_{n}^{\ast}$ and
$T\in\mathcal{M}_{n}$. There is a unique state $q$ of $T$ such that
$\pi_{T}(\gamma,q)=q$. Let $\nu\in W_{n}^{\ast}$ be a prime word such that
$\lambda_{T}(\gamma,q)$ is a power of $\gamma$. We set
$([\gamma]_{\sim_{{\mathmbox{rot}}}})(T)\Pi=[\nu]_{\sim_{{\mathmbox{rot}}}}$.
The map $\Pi:\mathcal{M}_{n}\to\mathop{\mathrm{Tr}}(\mathsf{W}_{n}^{\ast})$ is
an injective homomorphism.

##  3 A homomorphism

###  3.1 On $\mathcal{L}_{n}$

In the paper [19] a homomorphism is defined from
$\mathcal{O}_{n}\to\mathfrak{U}_{n-1}$ which restricts to a homomorphism from
$\mathcal{L}_{n}\to\mathfrak{U}_{,n-1n}$. We make use of an observation in the
paper [3] to extend this homomorphism from $\mathcal{L}_{n}$ to a quotient of
a submonoid of $\mathbb{N}$ by a certain congruence. We later show that the
kernel of this homomorphism is isomorphic to the _inert subgroup_ consisting
of elements of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$
belonging to the kernel of the _dimension representation_. We define these
terms in Section 4 where we make explicit the connection to the dimension
group.

We begin by defining first the map
$\overrightarrow{\mathrm{sig}}:\mathcal{O}_{n}\to\mathfrak{U}_{n-1}$.

######  Definition 3.1.

Let $T\in\mathcal{O}_{n}$ and $q\in Q_{T}$. Let $s\in\mathbb{N}_{1}$ be such
that there exists distinct pairwise incomparable elements
$\mu_{1},\mu_{2},\ldots,\mu_{s}\in X_{n}^{*}$ satisfying $\bigcup_{1\leq i\leq
s}U^{+}_{\mu_{i}}=\mathrm{Image}{(q)}$. Set
$(T)\overrightarrow{\mathrm{sig}}\in\mathfrak{U}_{n-1}$ to be equal to $s\
(\mathrm{mod}\ n-1)$.

The following results are from [19]:

######  Theorem 3.2.

Let $T\in\mathcal{O}_{n}$ then $(T)\overrightarrow{\mathrm{sig}}$ depends only
on $T$ moreover and induces a epimorphism from $\mathcal{O}_{n}$ onto the
group $\mathfrak{U}_{n-1,n}$.

######  Propostion 3.3.

Let $T\in\mathcal{O}_{n}$, and $1\leq r<n$, then $T\in T\in\mathcal{O}_{n,r}$
if and only if $r(T)\mathrm{sig}\equiv r\mod{n-1}$.

We compute the images under $\overrightarrow{\mathrm{sig}}$ of some elements
of $\mathcal{L}_{n}$. The elements in this example will be important later on.

######  Example 3.4.

Let $n\in\mathbb{N}_{2}$,
$p_{1},p_{2},\ldots,p_{l},r_{1},r_{2},\ldots,r_{l}\in\mathbb{N}_{1}$ be such
that $p_{1}^{r_{1}}p_{2}^{r_{2}}\ldots p_{l}^{r_{l}}$ is the prime
decomposition of $n$. For $1\leq i\leq l$ fix an alphabet $X_{p_{i}}$, $1\leq
i\leq l$, of size $p_{i}$, we also assume that for $i\neq j$, $X_{p_{i}}\cap
X_{p_{j}}=\emptyset$ . Set $X_{n}:=X_{p_{1}}^{r_{1}}\times
X_{p_{2}}^{r_{2}}\ldots\times X_{p_{l}}^{r_{l}}$. Fix $1\leq i\leq l$ and let
$N_{i}=p_{1}^{r_{1}}\cdot p_{2}^{r_{2}}\cdot\ldots\cdot
p_{i}^{r_{i}-1}\cdot\ldots\cdot p_{l}^{r_{l}}$.

Define a transducer $T(p_{i},N_{i})$ as follows. The state set of
$T(p_{i},N_{i})$ is precisely the set $\\{q_{x}\mid x\in X_{p_{i}}\\}$. The
transition and output function are given as follows: for $x\in X_{p_{i}}$ and
$\gamma:=\gamma_{1}\gamma_{2}\ldots\gamma_{l}\in X_{n}$, $\gamma_{j}\in
X_{p_{j}}^{r_{j}}$ for all $1\leq j\leq l$, set
$\pi_{T(p_{i},N_{i})}(\gamma,q_{x})=q_{y}$ if and only if $y$ is the last
letter of $\gamma_{i}$; set
$\lambda_{T(p_{i},N_{i})}(\gamma,q_{x}):=\gamma_{1}\gamma_{2}\ldots\gamma_{i}^{\prime}\gamma_{i+1}\ldots\gamma_{l}$
where $\gamma^{\prime}_{i}$ is obtained from $\gamma_{i}$ by deleting its
letter and appending letter $x$ to the resulting word, i.e
$\gamma^{\prime}_{i}=x\nu$ where $\nu$ is the length $r_{i}-1$ prefix of
$\gamma_{i}$.

It is clear that $T(p_{i},N_{i})$ is an element of
$\widetilde{\mathcal{L}_{n}}$, we show that is in facts an element of
$\mathcal{L}_{n}$ by examining its action on $X_{n}^{\mathbb{Z}}$.

The action of $T(p_{i},N_{i})$, with the trivial annotation on
$X_{n}^{\mathbb{Z}}$ is best seen as follows. Let
$(\gamma_{j})_{j\in\mathbb{Z}}\in X_{n}^{\mathbb{Z}}$, and for
$j\in\mathbb{Z}$, write
$\gamma_{j}={\gamma_{j}^{1}\gamma_{j}^{2}\ldots\gamma_{j}^{l}}$,
$\gamma_{j}^{k}\in X_{p_{k}}^{r_{k}}$, $1\leq k\leq l$. Then
$(\gamma_{j})_{j\in\mathbb{Z}})(T(p_{i},N_{i}),0)$ is the sequence
$(\delta_{j})_{j\in\mathbb{Z}}$ defined as follows. For $j\in\mathbb{Z}$,
$\delta_{j}={\gamma_{j}^{1}\gamma_{j}^{2}\ldots\gamma_{j}^{i-1}\delta_{j}^{i}\gamma_{j}^{i+1}\ldots\gamma_{j}^{l}}$
where $\delta_{j}^{i}$ is obtained from $\gamma_{j}^{i}$ by deleting its last
letter and appending the last letter of $\gamma_{j-1}^{i}$ to the resulting
word. From this, one sees that $(T(p_{i},N_{i}),0)$ is a shift-commuting
homeomorphism of $X_{n}^{\mathbb{Z}}$. Moreover, note that
$(\gamma_{j})_{j\in\mathbb{Z}})(T(p_{i},N_{i}),0)^{r_{i}}$ is the sequence
$(\nu_{j})_{j\in\mathbb{Z}}$ such that
$\nu_{j}={\gamma_{j}^{1}\gamma_{j}^{2}\ldots\gamma_{j}^{i-1}\gamma_{j-1}^{i}\gamma_{j}^{i+1}\ldots\gamma_{j}^{l}}$.

Observe that for $1\leq i_{1},i_{2}\leq l$ such that $i_{1}\neq i_{2}$,
$(T(p_{i_{1}},N_{i_{1}}),0)$ and $(T(p_{i_{2}},N_{i_{2}}),0)$ commute.

Fix a subset $i_{1},i_{2},\ldots,i_{t}$ of $\\{1,2,\ldots,l\\}$ such that
$i_{j}\leq i_{j^{\prime}}$ whenever $j\leq j^{\prime}$, and fix $s_{i_{j}}$
between $1$ and $r_{i_{j}}$. Set
$d:=p_{i_{1}}^{s_{i_{1}}}p_{i_{2}}^{s_{i_{2}}}\ldots p_{i_{t}}^{s_{i_{t}}}$,
and let $e\in\mathbb{N}$ be such that $de=n$. Generalising the construction
above, define a transducer $T(d,e)\in\mathcal{L}_{n}$ as follows.

The set of states of $T(d,e)$ is precisely the set $\\{q_{x}\mid x\in
X_{p_{i_{1}}}^{s_{i_{1}}}\times X_{p_{i_{2}}}^{s_{i_{2}}}\times\ldots\times
X_{p_{i_{t}}}^{s_{i_{t}}}\\}$. The transition and output are as follows. Given
$\gamma=\gamma_{1}\gamma_{2}\ldots\gamma_{l}\in X_{n}$, $\gamma_{j}\in
X_{p_{j}}^{r_{j}}$ for all $1\leq j\leq l$, and $x=x_{i_{1}}\ldots
x_{i_{t}}\in X_{p_{i_{1}}}^{s_{i_{1}}}\times\ldots\times
X_{p_{i_{t}}}^{s_{i_{t}}}$, set $\pi_{T(d,e)}(\gamma,q_{x})=q_{y}$ if and only
if $y$ is equal to the word
$\overline{\gamma}_{i_{1}}\overline{\gamma}_{i_{2}}\ldots\overline{\gamma}_{i_{t}}$,
for $\overline{\gamma}_{i_{j}}$, $1\leq j\leq t$, the length $s_{i_{j}}$
suffix of $\gamma_{i_{j}}$. Set
$\lambda_{T(d,e)}(\gamma,q_{x})=\delta_{2}\delta_{2}\ldots\delta_{l}$, where
for $j\in\\{i_{1},i_{2},\ldots,i_{t}\\}$, $\delta_{j}$ is obtained from
$\gamma_{j}$ by deleting the last $s_{j}$ letters of $\gamma_{j}$ and
appending $x_{j}$ to the resulting word.

The reader may verify that $T(d,e)$ is precisely the product
$(T(p_{i_{1}},N_{i_{1}}),0)^{s_{i_{1}}}(T(p_{i_{2}},N_{i_{2}}),0)^{s_{i_{2}}}\ldots(T(p_{i_{t}},N_{i_{t}}),0)^{s_{i_{t}}}$.

Observe that $(T(n,1),0)$ is the shift-map $\sigma_{n}$, one may also think of
$(T(1,n),0)$ (although not defined) as representing the identity map.

We now compute the value of $(T(d,e),0)\overrightarrow{\mathrm{sig}}$ for
$d,e\in\mathbb{N}$ such that $de=n$.

Let $d=p_{i_{1}}^{s_{i_{1}}}p_{i_{2}}^{s_{i_{2}}}\ldots
p_{i_{t}}^{s_{i_{t}}}$, where $i_{1}<i_{2}<\ldots<i_{t}$ are elements of
$\\{1,2,\ldots,l\\}$. Fix $x:=x_{i_{1}}\ldots x_{i_{t}}\in
X_{p_{i_{1}}}^{s_{i_{1}}}\times\ldots\times X_{p_{i_{t}}}^{s_{i_{t}}}$ a state
of $T(d,e)$. Let $V\subseteq X_{n}$ be the set of those elements
$\gamma_{1}\gamma_{2}\ldots\gamma_{l}$ such that for $1\leq j\leq t$,
$x_{i_{j}}$ is a prefix of $\gamma_{i_{j}}$. Notice that $|V|=e$ and the set
${\\{U^{+}_{\nu}\mid\nu\in V\\}}$ is precisely the image of the state $q_{x}$.
Therefore, $(T(d,e),0)\overrightarrow{\mathrm{sig}}=e\ (\mathrm{mod}\ n-1)$.

We define the submonoid of $\mathbb{N}$ and the congruence we will be
quotienting by.

Fix $n\in\mathbb{N}_{2}$. Let $p_{1},p_{2},\ldots,p_{r}$ be distinct prime
number and $l_{1},l_{2},\ldots,l_{r}\in\mathbb{N}_{1}$ such that
$n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}$. Let
$\mathfrak{M}(n):=\langle p_{1},p_{2},\ldots,p_{r}\rangle$ be the submonoid of
$\mathbb{N}$ generated by the distinct primes in the prime decomposition of
$n$. Let $\sim$ be the congruence on $\mathfrak{M}(n)$ defined by $a\sim b$ if
and only if there is some $l\in\mathbb{Z}$ such that $an^{l}=b$.

The group $\mathfrak{G}(n):=\mathfrak{M}(n)/\sim$ is a finitely generated
abelian group and is in fact isomorphic, in a natural way to the quotient of
the subgroup of $\mathbb{Q}\backslash\\{0\\}$ generated by the prime divisors
of $n$ by the group generated by $n$. Below we show that $\mathfrak{G}(n)$ is
isomorphic to $\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z}$ where
$n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}$ and
$l=\gcd(l_{1},l_{2},\ldots,l_{r})$.

######  Lemma 3.5.

Let $n\in\mathbb{N}_{2}$, $p_{1},p_{2},\ldots,p_{r}$ be distinct prime numbers
and $L_{1},L_{2},\ldots,L_{r}\in\mathbb{N}_{1}$ such that
$n=p_{1}^{L_{1}}p_{2}^{L_{2}}\ldots p_{r}^{L_{r}}$. Let
$l=\gcd(L_{1},L_{2},\ldots,L_{r})$ and set $l_{i}=L_{i}/l$ for $1\leq i\leq
r$. Then group $\mathfrak{G}(n)$ is isomorphic to
$\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z}$ where
$\mathbb{Z}^{r-1}\cong\langle p_{1},\ldots,p_{r-1}\rangle$ and
$\mathbb{Z}/l\mathbb{Z}\cong\langle p_{1}^{l_{1}}\ldots p_{r}^{l_{r}}\rangle$.

###### Proof.

Let $t\in\mathfrak{G}(n)$ be an non-trivial element of finite order. Write
$t=p_{1}^{s_{1}}p_{2}^{s_{2}}\ldots p_{r}^{s_{r}}$. We may assume that
$\gcd(s_{1},s_{2},\ldots,s_{r})=1$ since otherwise $t$ is a power of an
element $t^{\prime}$ of $\mathfrak{G}(n)$ and we may replace $t$ with
$t^{\prime}$. Let $k\in\mathbb{N}$ be such that $t^{k}=1\in\mathfrak{G}(n)$.
This means that $t^{k}=p_{1}^{ks_{1}}p_{2}^{ks_{2}}\ldots
p_{r}^{ks_{r}}\in\langle n\rangle$. This is true if and only if there is an
$m\in\mathbb{Z}$ such that $ks_{i}=mL_{i}$ for some $1\leq i\leq r$. Let
$d=\gcd(k,m)$ and set $k^{\prime}=k/d$ and $m^{\prime}=m/d$. It follows that
$k^{\prime}|L_{i}$ for all $i$ and so $k^{\prime}|l$. Write $l=sk^{\prime}$,
then and $L_{i}/k^{\prime}=sl_{i}$. Therefore
$t=(p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}})^{sm^{\prime}}\in\langle
p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}\rangle$.

Next observe that $\langle p_{1},\ldots,p_{r-1}\rangle\cong\mathbb{Z}^{r-1}$
and $\langle p_{1},\ldots,p_{r-1}\rangle\cap\langle
p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}\rangle=1$. This is a straight-
forward noting that for $t\in\langle p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots
p_{r}^{l_{r}}\rangle$ and $u\in\langle p_{1},\ldots,p_{r-1}\rangle$,
$tu^{-1}\notin\langle n\rangle$ unless $t=u=1$.

∎

######  Remark 3.6.

We note that $\mathfrak{G}(n)$ is a torsion group if and only if $n$ is a
power of strictly smaller integer. Moreover, $\mathfrak{G}(n)$ is trivial if
and only if $n$ is prime.

We now define an epimorphism from $\mathcal{L}_{n}$ to the group
$\mathfrak{G}(n)$. We require the following result is from [3].

######  Propostion 3.7.

Let $T\in\mathcal{L}_{n}$, then there is an element $P\in\mathcal{P}_{n}$ such
that the minimal representative of $P$ is $T$. Moreover, letting $[q]$ denote
the state of $T$ corresponding to a state $q\in Q_{P}$, the map from
$Q_{T}\to\mathbb{N}$ given by $[q]\mapsto\Lambda(\varepsilon,q)$ is a well-
defined annotation of $T$.

######  Remark 3.8.

There are a few consequences of this proposition. Firstly, observe that by the
strong synchronizing condition and results in [3], for a given element
$P\in\mathcal{P}_{n}$, there is a number $l\in\mathbb{N}$, and a divisor
$s\in\mathbb{N}$ of some power of $n$, such that for any state $q\in Q_{P}$,
there are elements $\mu_{1},\mu_{2},\ldots,\mu_{s}\in X_{n}^{l}$ and
$\bigcup_{1\leq i\leq s}U^{+}_{\mu_{i}}=\mathrm{Image}{(q)}$. The second thing
to observe, is that if $T$ is the minimal representative of $P$, then for
every $q\in Q_{P}$, the image of the state $[q]$ is the set
$\\{x-\Lambda(\varepsilon,q)\mid x\in\mathrm{Image}{(q)}\\}$. Let
$\alpha:Q_{T}\to\mathbb{N}$ be the annotation of $T$ such that
$[q]\mapsto\Lambda(\varepsilon,q)$. Then, we see that for every state $t\in
Q_{T}$, there are words
$\mu^{\prime}_{1},\mu^{\prime}_{2},\ldots,\mu^{\prime}_{s}\in
X_{n}^{l-([q])\alpha}$ such that $\bigcup_{1\leq i\leq
s}U^{+}_{\mu^{\prime}_{i}}=\mathrm{Image}{([q])}$. Set $s_{T}$ to be the
smallest number such that $s$ is equal to $s_{T}$ times some power of $n$.
Thus $s_{T}$ and $s$ represent the same element of $\mathfrak{G}(n)$. The last
thing we note is the following fact: let $\beta$ be any other annotation of
$T$, then for any states $[p],[q]\in Q_{T}$,
$([p])\beta+l-([p])\alpha=([q])\beta+l-([q])\alpha$. This follows from the
fact that there is an $m\in\mathbb{Z}$ such that $\beta=\alpha+m$ by
definition of annotations.

######  Definition 3.9.

Define a map
$\overrightarrow{\mathrm{sig}}_{\omega}:\mathcal{L}_{n}\to\mathfrak{G}(n)$ by
$T\mapsto s_{T}$.

We have the following result:

######  Propostion 3.10.

The following things hold:

  1. 1.

the map $\overrightarrow{\mathrm{sig}}_{\omega}$ is a surjective homomorphism;

  2. 2.

$\ker(\overrightarrow{\mathrm{sig}}_{\omega})\unlhd\mathcal{L}_{n,1}$;

  3. 3.

setting $\mathcal{K}_{n}:=\ker(\overrightarrow{\mathrm{sig}}_{\omega})$, we
have $\mathcal{L}_{n}\cong\mathcal{K}_{n}\rtimes\mathfrak{G}(n)$. Thus if $n$
is prime $\mathcal{L}_{n}=\mathcal{K}_{n}$.

###### Proof.

We first show that $\overrightarrow{\mathrm{sig}}_{\omega}$ is a homomorphism.

Let $\overline{U},\overline{T}\in\mathcal{L}_{n}$ and let
$T,U\in\mathcal{P}_{n}$ be such that $\overline{T}$ and $\overline{U}$ are the
minimal representatives of $T$ and $U$ respectively.

Let $s_{T}$ and $s_{U}$ be divisors of some power of $n$ and
$l_{T},l_{U}\in\mathbb{N}$, such that for any pair of states $q\in Q_{T}$,
$p\in Q_{U}$, there are words $\mu_{1},\ldots,\mu_{s_{T}}\in X_{n}^{l_{T}}$,
$\nu_{1}\ldots\nu_{s_{U}}\in X_{n}^{l_{U}}$, and,
$\mathrm{Image}{(q)}=\bigcup_{1\leq i\leq s_{T}}U^{+}_{\mu_{i}}$ and
$\mathrm{Image}{(p)}=\bigcup_{1\leq j\leq s_{U}}U^{+}_{\nu_{j}}$.

Let $(q,p)$ be a state of $T\ast U$ such that $(q,p)\in\mathrm{Core}(T\ast
U)$. Let $\mu_{1},\ldots,\mu_{s_{T}}\in X_{n}^{l_{T}}$, satisfy
$\mathrm{Image}{(q)}=\bigcup_{1\leq i\leq s_{T}}U^{+}_{\mu_{i}}$. For each
$1\leq i\leq s_{T}$, let $p_{i}=\pi_{T}(\mu_{i},p)$, and let
$\nu_{1,i},\nu_{2,i},\ldots,\nu_{s_{U},i}\in X_{n}^{l_{u}}$ satisfy,
$\mathrm{Image}{(p_{i})}=\bigcup_{1\leq j\leq s_{U}}U^{+}_{\nu_{j,i}}$. Then
it follows that $\mathrm{Image}{((q,p))}=\bigcup_{1\leq i\leq s_{T},1\leq
j\leq S_{U}}U^{+}_{\lambda_{U}(\mu_{i},p)\nu_{j,i}}$. Thus we see that for any
state $(q^{\prime},p^{\prime})$ of $\mathrm{Core}(T\ \ast U)$, there are
$\tau_{1},\tau_{2},\ldots,\tau_{s_{T}s_{U}}\in X_{n}^{l_{T}+l_{U}}$ such that
$\mathrm{Image}{((q^{\prime},p^{\prime}))}=\bigcup_{1\leq i\leq
s_{T}s_{U}}U^{+}_{\tau_{i}}$.

Finally observe that if $s$ is any divisor of a power of $N$ and
$l\in\mathbb{N}$, are such that any state $(p^{\prime},q^{\prime})\in Q_{P}$,
there are elements $\tau_{1},\tau_{2},\ldots,\tau_{s}\in X_{n}^{l}$ and
$\bigcup_{1\leq i\leq s}U^{+}_{\mu_{i}}=\mathrm{Image}{(q)}$. Then either
$s=n^{l_{U}+l_{T}-l}s_{T}s_{U}$ or $sn^{l-l_{U}-l_{T}}=s_{T}s_{U}$. In
particular, $s$ and $s_{T}s_{U}$ correspond to the same element of
$\mathfrak{G}(n)$. By Remark 3.8 the result follows, since $TU$, the product
of $T$ and $U$ in $\mathcal{L}_{n}$, is precisely the minimal representative
of $\mathrm{Core}(T\ast U)$.

Surjectivity of $\overrightarrow{\mathrm{sig}}_{\omega}$ is a consequence of
examples in constructed in the paper [19]. In that paper, for each prime $p$
dividing $n$, an example is constructed of an element $T\in\mathcal{L}_{n}$
for which $(T)\mathrm{sig}_{\omega}=p$. Alternatively, the transducers in
Example 3.4 are also valid.

Let $n=p_{1}^{a_{1}}p_{2}^{a_{2}}\ldots p_{r}^{a_{r}}$, and write
$N_{i}=n/p_{i}$ for each $1\leq i\neq r$. As noted in Example 3.4, the
elements $T(p_{i},N_{i})$ commute and
$(T(p_{i},N_{i}))\overrightarrow{\mathrm{sig}}_{\omega}=N_{i}$. In particular,
the map $\overrightarrow{\mathrm{sig}}_{\omega}$ is an isomorphism from
$\langle T(p_{i},N_{i})\mid 1\leq 1\leq r\rangle$ to the group
$\mathfrak{G}(n)$, since the product $\Pi_{1\leq i\leq
r}T(p_{i},N_{i})^{l_{i}}=\mathrm{id}$ in $\mathcal{L}_{n}$ and a word
$w\in\\{T(p_{i},N_{i})\mid 1\leq i\leq r\\}$ represents the trivial element of
$\mathcal{L}_{n}$ if and only if it is of the form $\Pi_{1\leq i\leq
r}T(p_{i},N_{i})^{al_{i}}$ for some $a\in\mathbb{N}$. Thus, the extension

$1\to\mathcal{K}_{n}\to\mathcal{L}_{n}\to\mathfrak{G}(n)$

splits.

A straightforward application of Proposition 3.3 shows that
$\mathcal{K}_{n}\leq\mathcal{L}_{n,1}$. This is because $T\in\mathcal{L}_{n}$
is an element of $\mathcal{K}_{n}$ if and only if for any state $q\in Q_{T}$,
the image of $q$ can be written as a union of a power of $n$ basic open sets.
∎

######  Notation 3.11.

Write $\mathcal{K}_{n}$ for the group
$\ker(\overrightarrow{\mathrm{sig}}_{\omega})$. Observe that an element
$T\in\mathcal{L}_{n,1}$ is an element of $\mathcal{K}_{n}$ if and only if for
some state $q\in Q_{T}$ (and so for any state of $T$), the image of $q$ can be
written as a union of a power of $n$ basic open sets.

###  3.2 On $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$

The paper [3] gives an epimorphism homomorphism from the group
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to the subgroup
$\mathfrak{U}_{n-1,n}$ of the group $\mathfrak{U}_{n-1}$ of units of
$\mathbb{Z}_{n-1}$ generated by the divisors of $n$. We make use of the
following proposition to extend this homomorphism to the direct product
$\Pi_{k\in\mathbb{N}_{1}}\mathfrak{U}_{n^{k}-1,n^{k}}$. We show that the
kernel of this new homomorphism is isomorphic to the group $\mathcal{K}_{n}$.
In a later section we show that this homomorphism is precisely the _dimension
representation_ , thus making the group $\mathcal{K}_{n}$ isomorphic to the so
called _inert subgroup_.

We begin by setting up some notation.

Fix $n,m\in\mathbb{N}$ and let $d\in\mathbb{N}_{1}$ be such that $n^{d}=m$.
There is an embedding from the monoid
$\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$ into the
monoid $\mathop{\mathrm{End}}\nolimits(X_{m}^{\mathbb{Z}},\sigma_{m})$ which
is given by ‘increasing the alphabet size’ as follows. Order the set
$X_{n}^{d}$ in the lexicographic ordering and let $\beta_{n,m}:X_{m}\to
X_{n}^{d}$ be the bijection that sends a number $i$ to the $i$th element of
$X_{n}^{d}$. Given $l\in\mathbb{N}$, we extend $\beta_{n,m}$ to a bijection
$(\beta_{n,m})_{l}:X_{m}^{l}\to X_{n}^{dl}$ by
$\gamma_{1}\gamma_{2}\ldots\gamma_{l}\mapsto(\gamma_{1})\beta_{n,m}(\gamma_{2})\beta_{n,m}\ldots(\gamma_{l})\beta_{n,m}$.
Given a sequence $x\in X_{m}^{\mathbb{Z}}$, write $(x)(\beta_{n,m})_{\infty}$
for the sequence $y\in X_{n}^{\mathbb{Z}}$ such that
$(x_{i})\beta_{n,m}=y_{id}y_{id+1}\ldots y_{(i+1)d-1}$. Note that
$(\beta_{n,m})_{\infty}:X_{m}^{\mathbb{Z}}\to X_{n}^{\mathbb{Z}}$ is a
homeomorphism. Moreover
$\sigma_{m}(\beta_{n,m})_{\infty}=(\beta_{n,m})_{\infty}\sigma_{n}^{d}$. Thus,
given $\phi\in\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n})$,
the map $(\beta_{n,m})_{\infty}\phi(\beta_{n,m})_{\infty}^{-1}$ is an element
of $\mathop{\mathrm{End}}\nolimits((X_{m})^{\mathbb{Z}},\sigma_{m})$. Write
$\sigma_{n,m}$ for the map
$(\beta_{n,m})_{\infty}\sigma_{n}(\beta_{n,m})_{\infty}^{-1}$ and note that
$\sigma_{n,m}^{d}=\sigma_{m}$. Let
$\mathrm{ext}_{n,m}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\mathop{\mathrm{Aut}}({X_{m}})$
denote the map which sends an element $\psi$ to
$\beta_{\infty}\psi\beta_{\infty}^{-1}$. Henceforth we no longer distinguish
between the maps $\beta_{n,m}$, $(\beta_{n,m})_{\infty}$ and
$(\beta_{n,m})_{l}$, $l\in\mathbb{N}$, as it will normally be clear from the
arguments which is meant. The following result is standard and so we do not
give a proof.

######  Propostion 3.12.

Let $n,m\in\mathbb{N}_{2}$ such that $m$ is a power of $n$. Let
$C_{\mathop{\mathrm{End}}\nolimits(X_{m}^{\mathbb{Z}},\sigma_{m})}(\sigma_{n,m}):=\\{\psi\in\mathop{\mathrm{End}}\nolimits(X_{m}^{\mathbb{Z}},\sigma_{m})\mid\psi\sigma_{{n,m}}=\sigma_{n,m}\psi\\}$
and
$C_{\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})}(\sigma_{n,m}):=\\{\psi\in\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})\mid\psi\sigma_{n,m}=\sigma_{n,m}\psi\\}$.
Then
$C_{\mathop{\mathrm{End}}\nolimits(X_{m}^{\mathbb{Z}},\sigma_{m})}(\sigma_{n,m})$
is precisely the monoid
$(\mathop{\mathrm{End}}\nolimits(X_{n}^{\mathbb{Z}},\sigma_{n}))\mathrm{ext}_{n,m}$
and $C_{\mathop{\mathrm{Aut}}({X_{m}^{\mathbb{Z}},\sigma_{m}})}(\sigma_{n,m})$
is precisely the group
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\mathrm{ext}_{n,m}$.

Clearly the map the composition of the natural map from
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})/\langle\sigma_{n}\rangle$,
yields a homomorphism from
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to
$\mathfrak{U}_{n-1,n}$. We will also denote this map by
$\overrightarrow{\mathrm{sig}}$. Below, we explicitly define this map
$\overrightarrow{\mathrm{sig}}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\mathfrak{U}_{n-1,n}$:
we give two equivalent definitions: the first using the representation of
elements of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ as an
element of $\langle\sigma_{n}\rangle F_{\infty}$ and the second using the
representation in terms of elements of $\mathcal{AL}_{n}$, that is in terms of
bi-synchronizing core transducers. Both points of view will be useful to us.

######  Definition 3.13.

Let $m\in\mathbb{N}$ and $f\in F(X_{n},m)$ so that $f_{\infty}\in
F_{\infty}(X_{n})$. Let $\gamma=\gamma_{-m+1}\ldots\gamma_{-1}\gamma_{0}\in
X_{n}^{m}$ and consider the clopen set $U^{0}_{\gamma}:=\\{x\in
X_{n}^{\mathbb{Z}}\mid x_{-m+1}\ldots x_{-1}x_{0}=\gamma\\}$. The image
$(U^{0}_{\gamma})f_{\infty}$ is clopen and so the set
$((U^{0}_{\gamma})f_{\infty})_{>0}:=\\{x_{1}x_{2}\ldots\mid\exists
y\in(U^{0}_{\gamma})f_{\infty}:y_{1}y_{2}\ldots=x_{1}x_{2}\ldots\\}$ is clopen
also. Let $r\in\mathbb{N}$, be minimal such that there exists elements
$\nu_{1},\nu_{2}\ldots\nu_{r}\in X_{n}^{*}$ satisfying $\cup_{1\leq i\leq
r}U^{+}_{\nu_{i}}={((U^{0}_{\gamma})f_{\infty})_{>0}}$. Set
$(f)\overrightarrow{\mathrm{sig}}=r\ (\mathrm{mod}\ n-1)$. More generally for
$k\in\mathbb{Z}$, set
$(\sigma_{n}^{k}f_{\infty})=(f_{\infty})\overrightarrow{\mathrm{sig}}$.

Alternatively, given $\psi=\sigma_{n}^{k}f_{\infty}$, $k\in\mathbb{N}$ and
$f\in F(X_{n},m)$ for some $m\in\mathbb{N}$, an element of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, $\psi=(L,\alpha)$
for some annotation $L\in\mathcal{L}_{n}$ and an annotation $\alpha$ of $L$.
Let $q\in Q_{L}$ be an arbitrary state, and let $r\in\mathbb{N}$ be minimal
such that there are $\nu_{1},\nu_{2}\ldots\nu_{r}\in X_{n}^{*}$ satisfying
$\cup_{1\leq i\leq r}U^{+}_{\nu_{i}}=\mathrm{Image}{(q)}$, then set
$(L,\alpha)\overrightarrow{\mathrm{sig}}=r\ (\mathrm{mod}\ n-1)$.

Below we make use of Proposition 3.12 to define an extension of the
homomorphism $\overrightarrow{\mathrm{sig}}$ and explore some implications of
this. For reasons which become clear later on we also write
$\mathrm{sig}_{\omega}$ for this homomorphism. We require the following
properties of the elements $T(p_{i},N_{i})$ of Example 3.4.

######  Lemma 3.14.

Let $r\in\mathbb{N}_{2}$, $p_{1}\ldots,p_{r}$ be distinct primes,
$l_{1},\ldots,l_{r}\in\mathbb{N}_{1}$ and $n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots
p_{r}^{l_{r}}$. Fix $1\leq i\leq r$, a word $w=w_{1}w_{2}\ldots
w_{l}\in(\\{1,\ldots,r\\}\backslash\\{i\\})^{\ast}$, then the product
$U:=T(p_{w_{1}},N_{w_{1}})\ast T(p_{w_{2}},N_{w_{2}})\ast\ldots\ast
T(p_{w_{l}},N_{w_{l}})$ has no states of incomplete response. Consequently,
setting $S$ to be the minimal representative of $U$, we have
$(T(p_{w_{1}},N_{w_{1}}),0)(T(p_{w_{2}},N_{w_{2}}),0)\ldots(T(p_{w_{l}},N_{w_{l}}),0)=(S,0)$.

###### Proof.

We use the description of the elements $T(p_{i},N_{i})$ as given in Example
3.4. That is, let $X_{p_{a}}$, $1\leq a\leq r$ be alphabets of size $p_{a}$,
and we think of an element of $X_{n}$ as a word $u_{r}u_{r-1}\ldots u_{1}$ for
$u_{a}\in X_{p_{a}}^{l_{a}}$, $1\leq a\leq r$. Let
$a\in\\{1,\ldots,r\\}\backslash\\{i\\}$ and $x\in X_{p_{a}}$ so that $q_{x}$
is a state of $T(p_{a},N_{a})$. Then for any element
$\gamma=\gamma_{r}\gamma_{r-1}\ldots\gamma_{1}$, $\gamma_{b}\in
X_{p_{b}}^{l_{b}}$, $1\leq b\leq r$, $\lambda_{T(p_{a},N_{a})}(\gamma,q_{x})$,
is the word obtained from $\gamma$, by deleting the last letter of
$\gamma_{a}$ and appending $x$ as a prefix to the resulting word. We thus
observe that $T(p_{a},N_{a})$ leaves the subword $\gamma_{i}$ unchanged.

Let $w_{1},w_{2},\ldots w_{l}\in\\{1,\ldots,r\\}\backslash\\{i\\}$, set
$U:=T_{w_{1}}\ast T_{w_{2}}\ast\ldots\ast T_{w_{l}}$ and let $q$ be an
arbitrary state of $U$. Then, given words
$\gamma=\gamma_{r}\ldots\gamma_{1},\delta=\delta_{r}\ldots\delta_{1}\in
X_{n}$, $\delta_{a},\gamma_{a}\in X_{p_{a}}^{l_{a}}$, such that the
$\gamma_{i}\neq\delta_{i}$, the previous paragraph implies that
$\lambda_{U}(\delta,q)\neq\lambda_{U}(\gamma,q)$. Thus we see that $U$ has no
states of incomplete response. Setting $S^{\prime}=\mathrm{Core}(U)$ and $S$
to be the minimal representative of $S^{\prime}$. We have that both $S$ and
$S^{\prime}$ are synchronous since $S^{\prime}$ has no states of incomplete
response. Moreover, as $S$ is precisely $S^{\prime}$ with $\omega$-equivalent
states identified, the equality $(S,0)=(S^{\prime},0)$ is valid. To conclude
we observe that $(S^{\prime},0)$ is precisely the map
$(T(p_{w_{1}},N_{w_{1}}),0)(T(p_{w_{2}},N_{w_{2}}),0)\ldots(T(p_{w_{l}},N_{w_{l}}),0)$.
∎

######  Corollary 3.15.

Let $r\in\mathbb{N}_{2}$, $p_{1}\ldots,p_{r}$ be distinct primes,
$l_{1},\ldots,l_{r}\in\mathbb{N}_{1}$ and $n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots
p_{r}^{l_{r}}$. Fix $1\leq i\leq r$, then the subgroup
$\langle(T(p_{j},N_{j}),0)\mid j\in\\{1,2,\ldots,r\\}\backslash\\{i\\}\rangle$
of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ is isomorphic to
the subgroup $\langle T(p_{j},N_{j})\mid
j\in\\{1,2,\ldots,r\\}\backslash\\{i\\}\rangle$ of $\mathcal{L}_{n}$.

In the statement of the theorem below, we write $\mathcal{K}_{n}$ for the
kernel of the map
$\overrightarrow{\mathrm{sig}}_{\omega}:\mathcal{L}_{n}\to\mathfrak{G}(n)$ and
we write $\ker(\overrightarrow{\mathrm{sig}}_{\omega})$ for the kernel of the
map
$\overrightarrow{\mathrm{sig}}_{\omega}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\Pi_{k\in\mathbb{N}}\mathfrak{U}_{n^{k}-1,n^{k}}$.
As we will see, these two groups are isomorphic.

######  Theorem 3.16.

The following things hold:

  1. 1.

There is a non-trivial homomorphism
$\overrightarrow{\mathrm{sig}}_{\omega}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\Pi_{k\in\mathbb{N}}\mathfrak{U}_{n^{k}-1,n^{k}}$,
given by
$\psi\mapsto(((\psi)\mathrm{ext}_{n,n^{k}})\overrightarrow{\mathrm{sig}})_{k\in\mathbb{N}}$.

  2. 2.

Thus, for each $k\in\mathbb{N}$, there is a homomorphism
$\overrightarrow{\mathrm{sig}}_{[k]}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\Pi_{1\leq
j\leq k}\mathfrak{U}_{n^{j}-1,n^{j}}$ and an epimorphism
$\overrightarrow{\mathrm{sig}}_{k}:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\mathfrak{U}_{n^{k}-1,n^{k}}$.

  3. 3.

The equality: rCl (Aut(X_n^Z,σ_n))$\overrightarrow{\mathrm{sig}}$_ω &=
(⟨(T(d,e),0) ∣d,e ∈N, de = n ⟩)$\overrightarrow{\mathrm{sig}}$
= ⟨(d (mod n-1),d,d …) ∣d  is a prime divisor of  n ⟩ is valid. In particular,
for any $\psi\in\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, there
exist prime numbers $e_{1},e_{2},\ldots,e_{l}$, depending only on $\psi$, such
that, taking $d_{i}\in\mathbb{N}$ satisfying $d_{i}e_{i}=n$, we have

$((T(d_{1},e_{1}),0)^{-1}(T(d_{2},e_{2}),0)^{-1}\ldots(T(d_{l},e_{l}),0)^{-1}\psi)\overrightarrow{\mathrm{sig}}_{\omega}=(1,1,1,\ldots).$

  4. 4.

The image
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}$
of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ under
$\overrightarrow{\mathrm{sig}}_{\omega}$ is a finitely generated torsion free
abelian group of rank equal to the number of prime divisors of $n$.

  5. 5.

Let $p_{1},p_{2},\ldots,p_{r}$ be distinct prime numbers and let
$l_{1},l_{2},\ldots,l_{r}$ be elements of $\mathbb{N}_{1}$ such that
$n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}$. Then,

    1. (a)

$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\cong\ker(\overrightarrow{\mathrm{sig}}_{\omega})\rtimes\mathbb{Z}^{r}\cong\mathcal{K}_{n}\rtimes\mathbb{Z}^{r}$;

    2. (b)

and
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\cong\mathcal{L}_{n}\times\mathbb{Z}$
if and only if $\gcd(l_{1},l_{2},\ldots,l_{r})=1$ (i.e $n$ is not a power of a
strictly smaller integer.)

###### Proof.

Parts 1 and 2 arise by combining Theorem 3.2 and Proposition 3.12.

We now consider 3. We begin with the last equality in the first sentence.

Let $k\in\mathbb{N}$, and let $d,e\in\mathbb{N}$ be such that $de=n$. Define a
transducer $T(d,e)_{k}=\langle
X_{n}^{k},Q_{T(d,e)},\pi_{T(d,e)_{k}},\lambda_{T(d,e)_{k}}\rangle$ as follows:
for $\gamma\in X_{n}^{k}$ and $q\in Q_{T(d,e)}$,
$\pi_{T(d,e)_{k}}(\gamma,q)=\pi_{T(d,e)}(\gamma,q)$ and
$\lambda_{T(d,e)_{k}}(\gamma,q)=\lambda_{T(d,e)}(\gamma,q)$. Then
$(T(d,e)_{k},0)$ defines an element of
$\mathop{\mathrm{Aut}}({X_{n^{k}}^{\mathbb{Z}},\sigma_{n^{k}}})$ moreover,
upto relabelling the alphabet, we have
$(T(d,e)_{k},0)=((T(d,e),0))\mathrm{ext}_{n,n^{k}}$.

It is straightforward to see that
$((T(d,e)_{k},0))\overrightarrow{\mathrm{sig}}=en^{k-1}$. This is because, as
computed in Example 3.4, for a state $q\in Q_{T(d,e))}$, there is a subset
$V_{q}$ of $X_{n}$ length $e$ such that $\mathrm{Image}{(q)}=\cup_{\nu\in
V_{q}}U^{+}_{\nu}$. It therefore follows that $\mathrm{Image}{(q)}$, thought
of now as a state of $T(d,e)_{k}$, is precisely:

$\bigcup_{\nu\in V_{q},\mu\in X_{n}^{k-1}}U^{+}_{\nu\mu}.$

We therefore see that

$((T(d,e),0))\overrightarrow{\mathrm{sig}}_{\omega}=(e\ (\mathrm{mod}\
n-1),en\ (\mathrm{mod}\ n^{2}-1),\ldots,en^{k-1}\ (\mathrm{mod}\
n^{k}-1),\ldots),$

and so

$((T(d,e),0)^{-1})\overrightarrow{\mathrm{sig}}_{\omega}=(d\ (\mathrm{mod}\
n-1),d,d,d,\ldots).$

We now consider the remainder of part 3. Note that since
$\sigma_{n}=(T(n,1),0)$ it suffices to show that for any element
$f_{\infty}\in F_{\infty}(X_{n})$, there is an element
$\psi\in\langle(T(d,e),0)\mid d,e\in\mathbb{N},de=n\rangle$ such that $(\psi
f_{\infty})\overrightarrow{\mathrm{sig}}_{\omega}=(1,1,1,\ldots)$.

Let $f_{\infty}\in F_{\infty}(X_{n})$ and let $m\in\mathbb{N}$ be such that
$f\in F(X_{n},m)$. Let $k\in\mathbb{N}$ and define a map $g$ from
$X_{n}^{mk}\to X_{n}^{k}$ by setting
$(\gamma_{m+k-1}\ldots\gamma_{1}\gamma_{0})g=(\gamma_{0}\gamma_{1}\ldots\gamma_{m+k-1})f_{k}$.
Thus one may define a map
$g_{\infty}:{(X_{n}^{k})^{\mathbb{Z}}}\to(X_{n}^{k})^{\mathbb{Z}}$. Observe
that, up to relabelling the alphabet,
$g_{\infty}=(f_{\infty})\mathrm{ext}_{n,n^{k}}$. We thus move freely between
the maps $g_{\infty}$ and $(f_{\infty})\mathrm{ext}_{n,n^{k}}$.

Fix a word $\Gamma:=\gamma_{-mk+1}\ldots\gamma_{-1}\gamma_{0}\in(X_{n}^{km})$
and consider the clopen set $U^{0}_{\Gamma}\subset X_{n^{k}}^{\mathbb{Z}}$. We
dually consider $U^{0}_{\Gamma}$ both as a subset of $X_{n^{k}}^{\mathbb{Z}}$
and $X_{n}^{\mathbb{Z}}$.

Note that
$((U^{0}_{\Gamma})g_{\infty})_{>0}=\\{\rho_{1}\rho_{2}\ldots\mid\rho_{i}\in
X_{n}^{k},i\in\mathbb{N}_{1}\mathrm{\ and\
}\rho_{1}\rho_{2}\ldots\in((U^{0}_{\Gamma})f_{\infty})_{>0}\\}$. That is,
$((U^{0}_{\Gamma})g_{\infty})_{>0}$ is precisely the set
$((U^{0}_{\Gamma})f_{\infty})_{>0}$ partitioned into blocks of length $k$
(from left to right). Thus,
$((f_{\infty})\mathrm{ext}_{n,n^{k}})\overrightarrow{\mathrm{sig}}$ is
congruent modulo $n^{k}-1$ to the minimal number $r$ such that there exist
$\mu_{1},\mu_{2},\ldots,\mu_{r}\in(X_{n}^{k})^{\ast}$ satisfying
${\left(\bigcup_{1\leq i\leq
r}U^{+}_{\mu_{i}}\right)}=((U^{0}_{\Gamma})f_{\infty})_{>0}$.

By a result in [3] there are minimal numbers $l,s\in\mathbb{N}$ such that $s$
is a divisor of some power of $n$ and there are
$\mu_{1},\mu_{2},\ldots,\mu_{s}\in X_{n}^{l}$ such that
$((U^{0}_{\Gamma})f_{\infty})_{>0}={\left(\bigcup_{1\leq i\leq
s}U^{+}_{\mu_{i}}\right)}$. Let $l^{-1}:=-l\ (\mathrm{mod}\ k)$, and let
$d_{1},d_{2},\ldots,d_{l},e_{1},e_{2},\ldots,e_{l}\in\mathbb{N}$ satisfy
$d_{i}e_{i}=n$ for all $1\leq i\leq l$ and $s=d_{1}d_{2}\ldots d_{l}$. Observe
that

${\left(\bigcup_{1\leq i\leq s,\ \nu\in
X_{n}^{l^{-1}}}U^{+}_{\mu_{i}\nu}\right)}=((U^{0}_{\Gamma})f_{\infty})_{>0},$

therefore

$(f_{\infty})\overrightarrow{\mathrm{sig}}_{k}=sn^{l^{-1}}\ (\mathrm{mod}\
n^{k}-1).$

Consider the map
$\psi=(T(d_{1},e_{1}),0)^{-1}(T(d_{2},e_{2}),0)^{-1}\ldots(T(d_{l},e_{l}),0)^{-1}f_{\infty}$.
It follows that $(\psi)\overrightarrow{\mathrm{sig}}_{k}=e_{1}\ldots
e_{l}\cdot s\cdot n^{l^{-1}}\ (\mathrm{mod}\ n^{k}-1)$. However, since
$e_{1}\ldots e_{l}\cdot s=n^{l}$ and $l+l^{-1}\equiv 0\ (\mathrm{mod}\ k)$ it
follows that $(\psi)\overrightarrow{\mathrm{sig}}_{k}=1$. Moreover, as the
product
$(T(d_{1},e_{1}),0)^{-1}(T(d_{2},e_{2}),0)^{-1}\ldots(T(d_{l},e_{l}),0)^{-1}$
depends only on $f_{\infty}$, then for any $k^{\prime}\in\mathbb{N}$,
$(\psi)\overrightarrow{\mathrm{sig}}_{k^{\prime}}=1$.

We may now deduce that $\overrightarrow{\mathrm{sig}}_{k}$ is surjective for
any $k\in\mathbb{N}$. For, as $\mathfrak{U}_{n^{k}-1,n^{k}}$ is precisely the
subgroup of $\mathfrak{U}_{n^{k}-1}$ generated by the divisors of $n^{k}$, it
is therefore also generated by the divisors of $n$ and by Part 3,
$\overrightarrow{\mathrm{sig}}_{k}$ is unto the divisors of $n$.

Part 4 follows since the generators are torsion free and commute.

Write $n=p_{1}^{l_{1}}\ldots p_{r}^{l_{r}}$, where $l_{i}>0$ and $p_{i}$ is
prime for all $1\leq i\leq r$; set $N_{i}=n/p_{i}$. By Part 3,
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})=\ker(\overrightarrow{\mathrm{sig}}_{\omega})\langle(T(p_{i},N_{i}),0)|1\leq
i\leq r\rangle$ and so we have
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})=\ker(\mathrm{sig}_{\omega})\rtimes\langle(T(p_{i},N_{i}),0)|1\leq
i\leq r\rangle$. It was demonstrated in Example 3.4 that
$\langle(T(p_{i},N_{i}),0)|1\leq i\leq r\rangle$ isomorphic to
$\mathbb{Z}^{r}$.

We now show that
$\ker(\overrightarrow{\mathrm{sig}}_{\omega})\cong\mathcal{K}_{n}$.

Let $\sigma_{n}^{-m}f_{\infty}\in\ker(\overrightarrow{\mathrm{sig}}_{\omega})$
for $f_{\infty}\in F_{\infty}(X_{n})$. There is an element
$T\in\mathcal{L}_{n}$ and an annotation $\alpha$ such that
$f_{\infty}=(T,\alpha)$. Moreover, by Proposition 3.7 we may assume
$\alpha:Q_{T}\to\mathbb{N}$. Let $\kappa$ be the canonical annotation of $T$,
then there is a $j\in\mathbb{Z}$ such that
$(T,\kappa)\sigma_{n}^{j}=f_{\infty}$. Thus, by results in [3] the map
$\kappa+j:Q_{T}\to\mathbb{Z}$ by $p\mapsto(p)\kappa+j$ is an annotation of $T$
and is equal to $\alpha$. Since there is a state of $T$ which takes value zero
under $\kappa$, as $\kappa$ is the canonical annotation, it follows that
$j\geq 0$.

Let $q\in Q_{T}$ be a state of $T$ such that $(q)\kappa=0$. Let
$k\in\mathbb{N}$ be such that $T$ is synchronizing at level $k$ and let
$l\in\mathbb{N}$ be such that there are elements $\mu_{1},\ldots,\mu_{s}\in
X_{n}^{l}$ satisfying $\bigcup_{1\leq i\leq
s}U^{+}_{\mu_{i}}=\mathrm{Image}{(q)}$. It simplifies our argument to assume
that $l>m$ and that $k$ is large enough such that for any word $\gamma\in
X_{n}^{kl}$, and any state $p\in Q_{T}$, $|\lambda_{T}(\gamma,p)|\geq j$.

Let $t\in\mathbb{N}$ be such that $ts=n^{l}$, since $s$ must be a divisor of a
power of $n$, $t$ exists. Fix, words $\Gamma,\Delta\in X_{n}^{kl}$ such that
the state of $T$ forced by ${\Gamma}$ is $q$, and consider the clopen set
$(U^{0}_{\Delta\Gamma})(T,\kappa))_{>0}$. Since $(q)\kappa=0$, it follows that
$(U^{0}_{\Delta\Gamma})(T,\kappa))_{>0}={\mathrm{Image}{(q)}}$.

Let $\rho$ be the length $j$ suffix of the word
${\lambda_{T}({\Gamma},q_{{\Delta}})}$. Since by definition
$(x)\sigma_{n}^{j}$ is the sequence $y$ satisfying $y_{i}=x_{i-j}$ for all
$i\in\mathbb{Z}$, it follows that
$(U^{0}_{\Gamma})(T,\kappa+j))_{>0}={\bigcup_{1\leq i\leq
s}U^{+}_{\rho\mu_{i}}}$. Thus
$(f_{\infty})\overrightarrow{\mathrm{sig}}_{l+j}=s$.

Let $a\in\mathbb{N}$ be such that $a\geq\max\\{l+j,m\\}$. Let $b\in\mathbb{N}$
be such that $b\equiv-(l+j)\ (\mathrm{mod}\ a)$, then,
$(f_{\infty})\overrightarrow{\mathrm{sig}}_{a}=sn^{b}$. Therefore we see that
$(\sigma_{n}^{-m}f_{\infty})\overrightarrow{\mathrm{sig}}_{a}=n^{m}sn^{b}\
(\mathrm{mod}\ n^{a}-1)$. This now implies that
$((\sigma_{n}^{-m}f_{\infty})\mathrm{sig}_{a})^{-1}=n^{a-m}t\mod{n^{a}-1}$.

If $n^{a-m}t\geq n^{a}$, then $t\geq n^{m}$ and $n^{a-m}t\equiv 1\
(\mathrm{mod}\ n^{a}-1)$ (since
$\sigma_{n}^{-m}f_{\infty}\in\ker(\overrightarrow{\mathrm{sig}}_{\omega})$).
Since this equation $n^{a-m}t\equiv 1\ (\mathrm{mod}\ n^{a}-1)$ is valid for
all $a\in\mathbb{N}_{1}$, it must be the case that $t=n^{m}$.

If $n^{a-m}t\leq n^{a}$, then, as $n^{a-m}t\equiv 1\ (\mathrm{mod}\ n^{a}-1)$
for all $a\in\mathbb{N}$, we must have that $n^{a-m}t=n^{a}$ and $t=n^{m}$.
Thus, in either case, it follows that $s=n^{l-m}$, which implies that
$T\in\mathcal{K}_{n}$.

On the other hand, given $T\in\mathcal{K}_{n}$ we show that there is a unique
annotation $\alpha$ of $T$ such that
$(T,\alpha)\in\ker(\overrightarrow{\mathrm{sig}}_{\omega})$.

Fix $T\in\mathcal{K}_{n}$. Let $\kappa$ be the canonical annotation of $T$ and
$q\in Q_{T}$ be a state such that $(q)\kappa=0$. Since $T\in\mathcal{K}_{n}$
there is are numbers $a,b\in\mathbb{N}_{1}$ and words
$\mu_{1},\mu_{2},\ldots,\mu_{n^{a}}\in X_{n}^{b}$ such that $\bigcup_{1\leq
i\leq n^{l}}U^{+}_{\mu_{i}}=\mathrm{Image}{(q)}$. Thus, it follows that for
arbitrary $d\in\mathbb{N}_{1}$, and $e\in\mathbb{Z}_{d}$ such that $b+e\equiv
0\mod{d}$,
$((T,\alpha))\overrightarrow{\mathrm{sig}}_{d}=n^{a+e}\mod{n^{d}-1}$. It is
now clear that
$(\sigma_{n}^{a-b}(T,\alpha))\overrightarrow{\mathrm{sig}}_{\omega}=(1,1,1,\ldots)$,
since
$(\sigma_{n}^{a-b})\overrightarrow{\mathrm{sig}}_{\omega}=(n^{b-a},n^{b-a},\ldots)$.

Observe that $\sigma_{n}^{a-b}(T,\alpha))=(T,\alpha+a-b)$. Moreover, for any
other annotation $\beta$ of $T$, there is an integer $i\in\mathbb{Z}$ such
that $(T,\beta)=(T,\alpha)\sigma_{n}^{i}$. Since $\sigma_{n}$ is not an
element of $\ker(\overrightarrow{\mathrm{sig}}_{\omega})$, it follows that
$\alpha$ is the unique annotation of $T$ such that
$(T,\alpha+a-b)\in\ker(\overrightarrow{\mathrm{sig}}_{\omega})$.

Thus we see that the map from
$\ker(\overrightarrow{\mathrm{sig}}_{\omega})\to\mathcal{L}_{n}$ by
$(T,\alpha)\mapsto T$ is an isomorphism. This proves 5a.

We now demonstrate 5b.

Fix $1\leq i\leq r$ and suppose that $n$ is not a power of a strictly smaller
integer, that is $\gcd(l_{1},l_{2},\ldots,l_{r})=1$. The proof of Proposition
3.10 and Lemma 3.5 shows that,
$\mathcal{L}_{n}\cong\mathcal{K}_{n}\rtimes\langle T(p_{j},N_{j})\mid 1\leq
j\leq r,\ j\neq i\rangle$. Therefore, by Corollary 3.15 the map from the
subgroup
$\ker(\overrightarrow{\mathrm{sig}}_{\omega})\langle(T(p_{i},N_{i}),0)\mid
1\leq j\leq r,\ j\neq i\rangle$ of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ to $\mathcal{L}_{n}$
sending $(T,\alpha)U\to TU$ for $U\in\langle T(p_{i},N_{i})\mid 1\leq i\leq
r-1\rangle$ is an isomorphism. Now as the group
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})/\langle\sigma_{n}\rangle\cong\mathcal{L}_{n}$,
we see that the extension
$1\to\langle\sigma_{n}\rangle\to\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\mathcal{L}_{n}$
splits and so
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\cong\ln\times\mathbb{Z}$.

If $n$ is a power of a proper integer, then
$\sigma_{n}\in\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ has
proper roots. For example setting $d$ to be the
$\gcd(l_{1},l_{2},\ldots,l_{r})$,

$\prod_{1\leq i\leq r}(T(p_{i},N_{i}),0)^{\frac{l_{i}}{d}}$

is a root of $\sigma_{n}$. This now means that
$\mathop{\mathrm{Aut}}({X_{n}^{*},\sigma_{n}})$ cannot be written as
$\langle\sigma_{n}\rangle$ and some subgroup
$L\leq\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, since $L$ must
necessarily have non-trivial intersection with $\sigma_{n}$. ∎

######  Corollary 3.17.

Let $n\in\mathbb{N}_{2}$, $p_{1},p_{2},\ldots,p_{r}$ be distinct primes, and
$l_{1},\ldots,l_{r}\in\mathbb{N}_{1}$, such that
$n=p_{1}^{l_{1}}p_{2}^{l_{2}}\ldots p_{r}^{l_{r}}$. Set
$G:=(\langle(\sigma_{n})\overrightarrow{\mathrm{sig}}_{\omega}\rangle)\overrightarrow{\mathrm{sig}}_{\omega}^{-1}$
a subgroup of $\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ and
$l=\gcd(l_{1},l_{2},\ldots,l_{r})$. Then,

  1. 1.

$G$ is a normal subgroup of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$;

  2. 2.

$G\cong\mathcal{K}_{n}\times\mathbb{Z}$ and there is a short-exact sequence:

$1\to
G\to\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to\mathbb{Z}^{r-1}\times\mathbb{Z}/l\mathbb{Z};$

  3. 3.

if $n$ is prime,
$G=\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\cong\mathcal{L}_{n}\times\mathbb{Z}$.

###### Proof.

For $1\leq i\leq r$ let $N_{i}=n/p_{i}$.

By Theorem 3.16,
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}=\langle(T(N_{i},p_{i}),0))\overrightarrow{\mathrm{sig}}_{\omega}\mid
1\leq i\leq r\rangle$. The quotient
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}/(\langle\sigma_{n}\rangle)\overrightarrow{\mathrm{sig}}_{\omega}$,
is the quotient of $\mathbb{Z}^{r}$ by the subgroup
$\\{(ml_{1},ml_{2},\ldots,ml_{r})\mid m\in\mathbb{Z}\\}$. It is not hard to
see that the torsion subgroup of
$\mathbb{Z}^{r}/\langle(l_{1},l_{2},\ldots,l_{r})\rangle$ is precisely the
subgroup
$\langle(\nicefrac{{l_{1}}}{{l}},\nicefrac{{l_{2}}}{{l}},\ldots,\nicefrac{{l_{r}}}{{l}})\rangle$.
By the third isomorphism theorem, we have:

$\dfrac{\left(\dfrac{\mathbb{Z}^{r}}{\langle(l_{1},l_{2},\ldots,l_{r})\rangle}\right)}{\left(\dfrac{\langle(\nicefrac{{l_{1}}}{{l}},\nicefrac{{l_{2}}}{{l}},\ldots,\nicefrac{{l_{r}}}{{l}})\rangle}{\langle(l_{1},l_{2},\ldots,l_{r})\rangle}\right)}\cong\dfrac{\mathbb{Z}^{r}}{\langle(\nicefrac{{l_{1}}}{{l}},\nicefrac{{l_{2}}}{{l}},\ldots,\nicefrac{{l_{r}}}{{l}})\rangle}.$

As the group $\langle(1,1,\ldots,1,0)\rangle$ is a finite index subgroup of
$\mathbb{Z}^{r}/\langle(\nicefrac{{l_{1}}}{{l}},\nicefrac{{l_{2}}}{{l}},\ldots,\nicefrac{{l_{r}}}{{l}})\rangle$,
we deduce that
$\mathbb{Z}^{r}/\langle(\nicefrac{{l_{1}}}{{l}},\nicefrac{{l_{2}}}{{l}},\ldots,\nicefrac{{l_{r}}}{{l}})\rangle\cong\mathbb{Z}^{r-1}$.

Let
$\psi:\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}/(\langle\sigma_{n}\rangle)\overrightarrow{\mathrm{sig}}_{\omega}$,
be the composition of $\overrightarrow{\mathrm{sig}}_{\omega}$ with the
natural map from
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}$
to the quotient
$(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}/(\langle\sigma_{n}\rangle)\overrightarrow{\mathrm{sig}}_{\omega}$.
It is clear that $\ker(\psi)$ is precisely the group $G$. Moreover, it is also
clear that, $\langle\\{((T(N_{i},p_{i}),0)\psi\mid 1\leq
i<r\\}\sqcup\\{(T(N_{r},p_{r}),0)^{j}\psi\mid 1\leq
j<l_{r}\\}\rangle=(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\psi$.
This is because, $(\Pi_{1\leq i\leq
r}(T(N_{i},p_{i}),0)^{l_{i}})\psi\in\langle(\sigma_{n})\psi\rangle$ which is
trivial. Thus we see that, there is a short exact sequence

$1\to
G\to\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})\to(\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}))\overrightarrow{\mathrm{sig}}_{\omega}/(\langle\sigma_{n}\rangle)\overrightarrow{\mathrm{sig}}_{\omega}.$

In particular, any element of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$, can be written as a
product $gt\sigma_{n}^{j}$, for $g\in G$, $t$ a product of an element of
$\langle\\{((T(N_{i},p_{i}),0)\psi\mid 1\leq i<r\\}\rangle$ with an element of
$\\{(T(N_{r},p_{r}),0)^{j}\mid 1\leq j<l_{r}\\}$, and $j\in\mathbb{Z}$.

The homomorphism
$\overrightarrow{\mathrm{sig}}_{\omega}\mathord{\upharpoonright}_{G}$ has
image precisely
$\langle(\sigma_{n})\overrightarrow{\mathrm{sig}}_{\omega}\rangle$, thus the
short exact sequence

$1\to\ker(\overrightarrow{\mathrm{sig}}_{\omega}\mathord{\upharpoonright}_{G})\to
G\to(G)\overrightarrow{\mathrm{sig}}_{\omega}$

splits. Since $\sigma_{n}$ commutes with every element of $G$ we see that
$G=\ker(\overrightarrow{\mathrm{sig}}_{\omega}\mathord{\upharpoonright}_{G})\times\langle\sigma_{n}\rangle$.
Clearly, by definition of the group $G$,
$\ker(\overrightarrow{\mathrm{sig}}_{\omega}\mathord{\upharpoonright}_{G})=\ker(\overrightarrow{\mathrm{sig}}_{\omega})$.
Thus by Theorem 3.16
$\ker(\overrightarrow{\mathrm{sig}}_{\omega}\mathord{\upharpoonright}_{G})\cong\mathcal{K}_{n}$.

Part 3. follows from the previous part, since when $n$ is prime, $r=1$, and
$\mathcal{K}_{n}=\mathcal{L}_{n}$. ∎

######  Corollary 3.18.

Let $n\in\mathbb{N}_{2}$, then,
$[\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}}),\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})]\cong[\mathcal{L}_{n},\mathcal{L}_{n}]\cong[\mathcal{K}_{n},\mathcal{K}_{n}]$.
∎

######  Corollary 3.19.

The order problem in $\mathcal{K}_{n}$ is undecidable.

###### Proof.

By a result of [16], the order problem in
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ is undecidable, the
result now follows Theorem 3.16.

∎

We note that it is a result of [3] that the groups $\mathcal{O}_{n,r}$, $1\leq
r\leq n-1$, have unsolvable order problem. This now also follows from the
corollary above since
$\mathcal{K}_{n}\unlhd\mathcal{L}_{n,1}\leq\mathcal{O}_{n,1}\leq\mathcal{O}_{n,r}$.

##  4 Reversing arrows and the dimension group

In this section we show that the operation of “reversing arrows” as described
in Subsection 4.3 induces an automorphism of $\mathcal{O}_{n}$. We note that
the homeomorphism of $\rho$ of $X_{n}^{\mathbb{Z}}$ that sends a sequence
$x\in X_{n}^{\mathbb{Z}}$ to the element $y\in X_{n}^{\mathbb{Z}}$ such that
$y_{i}=x_{-i}$, induces, by conjugation, an automorphism of
$\mathop{\mathrm{Aut}}({X_{n}^{\mathbb{Z}},\sigma_{n}})$ sending the shift map
to its inverse. Therefore, the map $\rho$ induces an automorphism of
$\mathcal{L}_{n}$. This automorphism corresponds precisely to “reversing
arrows” of the elements of $\mathcal{L}_{n}$. Thus one may recover a
representative in $\mathcal{L}_{n}$. Combinatorially, we note that the map
$\overleftarrow{\phantom{a}}:X_{n}^{k}\to X_{n}^{k}$ induces a bijection, an
involution, from $\mathsf{W}_{n}^{k}$ to itself for all $k\in\mathbb{N}$. Thus
conjugation by this bijection induces an automorphism of
$\mathrm{Sym}(\mathsf{W}_{n}^{\ast})$. An interpretation of the results of
this section is that $(\mathcal{O}_{n})\Pi$ (see Subsection 2.5.2 for the
definition of the map $\Pi:\mathcal{O}_{n}\to\mathrm{Sym}(W_{n}^{\ast})$) is
normalised by the bijection
$\overleftarrow{\phantom{a}}:\mathsf{W}_{n}^{\ast}\to\mathsf{W}_{n}^{\ast}$.
Since $(\mathcal{O}_{n})\Pi\leq\mathrm{Sym}(\mathsf{W}_{n}^{\ast})$ is
isomorphic to $\mathcal{O}_{n}$ we obtain an automorphism of
$\mathcal{O}_{n}$. We note that for $T\in\mathcal{O}_{n}$, the bijection on
the induced circuits of $\overleftarrow{T}$ from $\mathsf{W}_{n}^{\ast}$ to
itself, is precisely the map
$\overleftarrow{\phantom{a}}(T)\Pi\overleftarrow{\phantom{a}}$. To prove the
main result of this section we develop a procedure that associates to each
element $T\in\mathcal{O}_{n}$ an element $U\in\mathcal{O}_{n}$ such that
$(U)\Pi=\overleftarrow{\phantom{a}}(T)\Pi\overleftarrow{\phantom{a}}$ (note
that $U$ must be unique as
$\Pi:\mathcal{O}_{n}\to\mathrm{Sym}(\mathsf{W}_{n}^{\ast})$ is a faithful
representation ).

We begin by introducing non-deterministic transducers.

###  4.1 Non-deterministic, strongly synchronizing transducers

In this subsection we often have to distinguish between equality in the monoid
$X_{n}^{*}$ and equality of words. Therefore, given elements
$w_{1},\ldots,w_{l},u_{1},\ldots,u_{m}\in X_{n}\sqcup\\{\varepsilon\\}$, we
write $w_{1}\ldots w_{l}=u_{1}\ldots u_{m}$ if and only if $l=m$ and
$w_{i}=u_{i}$ for all $1\leq i\leq m$; we write $w_{1}\ldots w_{l}\equiv
u_{1}\ldots u_{m}$ if and only if $w_{1}\ldots w_{l}$ and $u_{1}\ldots u_{l}$
represent the same element of the monoid $X_{n}^{*}$.

A non-deterministic automaton $A=\langle X_{n},Q_{A},\pi_{A}\rangle$ is a
labelled directed graph with a finite vertex/state set $Q_{A}$, a finite edge
set $\pi_{A}\subseteq X_{n}^{\ast}\times Q_{A}\times Q_{A}$
($|\pi_{A}|<\infty$) and a finite alphabet set $X_{n}$. In other words, a non-
deterministic automaton is a finite directed graph with a finite number edges
between states and with edges labelled by elements of $X_{n}^{*}$.

Let $A$ be a non-deterministic automaton, a path in $A$ is a word

$(w_{1},p_{1},q_{1}),(w_{2},p_{2},q_{2}),\ldots,(w_{m},p_{m},q_{m})\in\pi_{A}^{\ast}$

such that $q_{i}=p_{i+1}$ for $1\leq i\leq m-1$. To simplify notation, we
write $(w,p_{1},q_{m})$ for the path
$(w_{1},p_{1},q_{1}),(w_{2},p_{2},q_{2}),\ldots,(w_{m},p_{m},q_{m})$ where
$w=w_{1}w_{2}\ldots w_{m}$.

We impose the following non-degeneracy condition on all non-deterministic
automata in this article: for any circuit $(w,p,p)$, $w\not\equiv\varepsilon$.

Let $A$ be a non-deterministic automaton. For a state $q\in Q_{A}$, we define
$\mathrm{Domain}{(q)}\subseteq X_{n}^{\mathbb{N}}$ as follows. Let $x\in
X_{n}^{\omega}$ be such that for any non-empty proper prefix $x_{i}$ of $x$
there are elements $w_{1},w_{2},\ldots,w_{m},w\in X_{n}^{*}$, with $x_{i}$ a
prefix of $w$, states $p_{0}=q,p_{1},\ldots,p_{m}\in Q_{A}$, such that
$(w_{i},p_{i-1},p_{i})$ is an element of $\pi_{A}$ for all $1\leq i\leq m$ and
$w_{1}w_{2}\ldots w_{m}\equiv w$. Then $x\in\mathrm{Domain}{(q)}$.

A non-deterministic automaton $A=\langle X_{n},Q_{A},\pi_{A}\rangle$ is called
strongly synchronizing if it satisfies the following condition. For any word
$u\in X_{n}^{+}$, there is a unique (up-to rotation) sequence

$(w_{1},p_{1},p_{2}),(w_{2},p_{2},p_{3}),\ldots,(w_{m},p_{m},p_{m+1})\in\pi_{A}$

with $p_{m+1}=p_{1}$ such that for $v\in X_{n}^{+}$ with $v\equiv w_{1}\ldots
w_{m}$, the equality
$[v]_{\sim_{{\mathmbox{rot}}}}=[u]_{\sim_{{\mathmbox{rot}}}}$ holds.

The collision with terminology in Subsection 2.4 is deliberate as Remark 4.1
makes clear. An interpretation of Proposition 4.10 is that strongly
synchronzing non-deterministic automaton and strongly synchronizing automaton
are essentially “the same thing”.

A strongly synchronizing non-deterministic automaton $A$ is called _core_ if
it is strongly connected.

######  Remark 4.1.

Every strongly synchronizing automaton is a strongly synchronizing non-
deterministic automaton. On the other hand any deterministic automaton which
is strongly synchronizing in the non-deterministic sense in strongly
synchronizing in the deterministic sense. That is the two notions of being
“strongly synchronizing” coincide on the class of deterministic automata.

######  Remark 4.2.

Let $A$ be a strongly synchronizing non-deterministic automaton. Given a prime
word $u\in X_{n}^{+}$, the unique circuit
$(w_{1},p_{1},p_{2})(w_{2},p_{2},p_{3})\ldots(w_{m},p_{m},p_{m+1})$ in $A$
with $w_{1}\ldots w_{m}$ equivalent to an element of
$[u]_{\sim_{{\mathmbox{rot}}}}$, is a prime word in $\pi_{A}^{\ast}$. This
follows from the non-degeneracy condition and the fact that $u$ is a prime
word. On the other hand, given a circuit
$(w_{1},p_{1},p_{2})(w_{2},p_{2},p_{3})\ldots(w_{m},p_{m},p_{m+1})$ in $A$
which is a prime word in $\pi_{A}^{\ast}$, the word $w_{1}\ldots w_{m}$ is
equivalent to a prime word in $X_{n}^{*}$. This follows from the existence and
uniqueness clause in the definition of strongly synchronizing automata. Thus
it follows that given a strongly synchronizing automaton $A$, there will be
circuits in $A$ which are prime words in $\pi_{A}$.

######  Remark 4.3.

Let $A$ be a strongly synchronizing non-deterministic automaton with alphabet
set $X_{n}$ and only one state. Then $A$ is the single state automaton with
$n$ edges each labelled with a unique element of $X_{n}$.

A non-deterministic transducer $T$ is a tuple $T=\langle
X_{n},Q_{T},\pi_{T},\lambda_{T}\rangle$ where $I(T)=\langle
X_{n},Q_{T},\pi_{T}\rangle$ is a (non-degenerate) non-deterministic automaton
called the input automaton, and, an output function $\lambda_{T}:\pi_{T}\to
X_{n}^{\ast}$. We identify a non-deterministic transducer with a labelled
digraph whereby an edge $(w,p,q)$ of $I(T)$ is labelled
$w|\lambda_{T}(w,p,q)$.

Let $p_{1},\ldots,p_{m+1}\in Q_{T}$ and $w_{1},\ldots,w_{m}\in X_{n}^{*}$ such
$(w_{i},p_{i},p_{i+1})$ is an element of $\pi_{T}$ for all $1\leq i\leq m$.
Then, setting $w=w_{1}\ldots w_{m}$, we write $\lambda_{T}(w,p_{1})$ for the
word $\lambda_{T}(w_{1},p_{1},p_{2})\ldots\lambda_{T}(w_{m},p_{m},p_{m+1})$
and write $(w,p_{1},p_{m+1})$ for the path
$(w_{1},p_{1},p_{2})(w_{2},p_{2},p_{3})\ldots(w_{m},p_{m},p_{m+1})$ labelled
$w$ from $p_{1}$ to $p_{m+1}$. Setting $\mathsf{w}\in\pi_{T}^{\ast}$ to be the
path $(w_{2},p_{2},p_{3})\ldots(w_{m},p_{m},p_{m+1})$ we write
$\lambda_{T}(\mathsf{w})$ for the word
$\lambda_{T}(w_{1},p_{1},p_{2})\ldots\lambda_{T}(w_{m},p_{m},p_{m+1})$.

We impose the following non-degeneracy condition on all non-deterministic
transducers in this article: for any circuit $(w,p,p)$,
$\lambda_{T}(w,p,p)\not\equiv\varepsilon$.

We identify the output function $\lambda_{T}$ with a subset of
$X_{n}^{*}\times Q_{T}\times Q_{T}$. Thus, the non-degeneracy condition above
means that the tuple $O(T)=\langle X_{n},Q_{T},\lambda_{T}\rangle$ is also a
non-deterministic automaton called the output automaton. Thus, the labelled
digraph for the input automaton of $T$ is obtained by deleting output words in
the digraph of the transducer; likewise the digraph for the output automaton
of $T$ is obtained by input words in the labelled digraph of $T$.

For a non-deterministic transducer $T$ and $q\in Q_{T}$, we identify
$\mathrm{Domain}{(q)}$ with $\mathrm{Domain}{(q)}$ as a state of $I(T)$.

At this point, one might expect the definition of the image
$\mathrm{Image}{(q)}$ of a state $q$ of a non-deterministic transducer $T$ and
the corresponding map
$\lambda_{T}(\cdot,q):\mathrm{Domain}{(q)}\to\mathrm{Image}{(q)}$. However,
for a general non-deterministic transducer, the map
$\lambda_{T}(\cdot,q):\mathrm{Domain}{(q)}\to\mathrm{Image}{(q)}$ is a
multifunction.

Let $T$ be a non-deterministic automaton. Then $T$ is called strongly
synchronizing if $I(T)$ is strongly synchronizing; $T$ is called bi-
synchronizing if both $I(T)$ and $O(T)$ are strongly synchronizing. If $T$ is
strongly synchronizing or bi-synchronizing, then $T$ is called core if its
input automaton is core.

The results that follow demonstrate that if we restrict to the class of
strongly-synchronizing transducers, the proposed map $\lambda_{T}$ is in fact
a well-defined function.

The following function will be used regularly in the proofs that follow.

######  Definition 4.4.

Let $A$ be a non-deterministic automaton or non-deterministic transducer. For
a state $q\in Q_{A}$ define a function $L_{q}:X_{n}^{*}\to\pi_{A}^{\ast}$ as
follows. Set $(\varepsilon)L_{q}=\varepsilon$; for a word $w\in X_{n}^{+}$ we
set $(w)L_{q}$ to be the greatest common prefix of the set of all infinite
paths, $(u_{1},p_{1},p_{2})(u_{2},p_{2},p_{3})\ldots\in\pi_{A}^{\mathbb{N}}$
where $p_{1}=q$ and $w$ is equivalent in $X_{n}^{*}$ to a prefix of
$u_{1}u_{2}u_{3}\ldots$.

######  Lemma 4.5.

Let $A$ be a core strongly synchronizing non-deterministic automaton. There is
an $N\in\mathbb{N}$ such that the following holds. Let $q\in Q_{A}$,
$x\in\mathrm{Domain}{(q)}$, paths $(w,q,p)$ and $(w^{\prime},q,p^{\prime})$ in
$A$ and words $\mu,\mu^{\prime}\in X_{n}^{*}$, both beginning with the length
$N$ prefix $x_{[1,N]}$ of $x$ be given. If $\mu\equiv w$ and
$\mu^{\prime}\equiv w^{\prime}$, then the paths $(w,q,p)$ and
$(w,q,p^{\prime})$, as words in $\pi_{A}^{\ast}$, have a non-empty prefix in
common.

###### Proof.

It suffices to show that there is an $N\in\mathbb{N}$ such that given $q\in
Q_{T}$, and any word $\nu\in X_{n}^{N}$ which is a prefix of an element of
$\mathrm{Domain}{(q)}$, $(\nu)L_{q}\neq\varepsilon$.

Let $d\in\mathbb{N}$ be such that for any element $(w,s,t)\in\pi_{A}$, $w$ is
equivalent to a word of length at most $d$ in $X_{n}^{*}$. (We note that $d$
since $A$ has finitely many edges.) Set

$N:=\left(\frac{n^{d+1}-1}{n-1}\right)|Q_{A}|+1$

noting that $\sum_{i=0}^{d}n^{i}=(n^{d+1}-1)/(n-1)$ is the size of the set of
all words of length at most $d$.

Let $\nu\in X_{n}^{N}$ be a prefix of an element of $\mathrm{Domain}{(q)}$ and
suppose $(\nu)L_{q}=\varepsilon$. Let

$(w_{1},q=q_{0},q_{1})(w_{2},q_{1},q_{2})...(w_{a},q_{a-1},q_{a})$

and

$(u_{1},q=p_{0},p_{1})(u_{2},p_{1},p_{2})...(p_{b},p_{b-1},p_{b})$

be paths beginning at $q$ such that
$(w_{1},q_{0},q_{1})\neq(u_{1},p_{0},p_{1})$ and $\nu$ is equivalent to a
prefix of both $w_{1}w_{2}\ldots w_{a}$ and $u_{1}u_{2}\ldots u_{a}$. For
$1\leq i\leq|\nu|$, let $\nu_{[1,i]}$ be the length $i$ prefix of $\nu$. For
each $1\leq i\leq|\nu|$, set
$(w_{1},q_{0},q_{1})(w_{2},q_{1},q_{2})...(w_{a_{i}},q_{a_{i}-1},q_{a_{i}})$
and
$(u_{1},p_{0},p_{1})(u_{2},p_{1},p_{2})...(u_{b_{i}},p_{b_{i}-1},p_{b_{i}})$
to be, respectively, the maximal prefixes of
$(w_{1},q=q_{0},q_{1})(w_{2},q_{1},q_{2})...(w_{a},q_{a-1},q_{a})$ and
$(u_{1},q=p_{0},p_{1})(u_{2},p_{1},p_{2})...(p_{b},p_{b-1},p_{b})$ such that
$w_{1}w_{2}\ldots w_{a_{i}}$ and $u_{1}\ldots u_{b_{i}}$ are equivalent to
prefixes of $\nu_{i}$. Define $\alpha_{i}$ and $\beta_{i}$ as the unique
elements of $X_{n}^{*}$ such that $\nu_{i}$ is equivalent to $w_{1}w_{2}\ldots
w_{a_{i}}\alpha_{i}$ and $\nu_{i}$ is equivalent $u_{1}\ldots
u_{b_{i}}\beta_{i}$. Note that $|\alpha_{i}|,|\beta_{i}|\leq d$. By choice of
$N=|\nu|$, there are $i_{1}$ and $i_{2}$ such that
$(q_{a_{i_{1}}},\alpha_{i_{1}})=(q_{a_{i_{2}}},\alpha_{i_{2}})$ and
$(p_{b_{i_{1}}},\beta_{i_{1}})=(p_{b_{i_{2}}},\beta_{i_{2}})$. Set
$\alpha=\alpha_{i_{1}}$ and $\beta=\beta_{i_{1}}$.

Without loss of generality we assume $|\alpha|\leq|\beta|$. Let
$\nu(\alpha)_{i_{1}},\nu(\beta)_{i_{1}}\in X_{n}^{*}$ be, respectively,
equivalent to $w_{1}\ldots w_{a_{i_{1}}}$ and $u_{1}\ldots u_{b_{i_{1}}}$. Now
as $|\alpha|\leq|\beta|$, there is a $\xi\in X_{n}^{*}$ such
$\nu(\alpha)_{i_{1}}=\nu(\beta)_{i_{1}}\xi$. Since
$\nu(\alpha)_{i_{1}}\alpha=\nu(\beta)_{i_{1}}\beta=\nu_{i_{1}}$ it follows
that $\beta=\xi\alpha$.

Consider the paths

$(w_{a_{i_{1}}+1},q_{a_{i_{1}}},q_{a_{i_{1}}+1})\ldots(w_{a_{i_{2}}},q_{a_{i_{2}}-1},q_{a_{i_{2}}})$

and

$(u_{b_{i_{1}}+1},p_{b_{i_{1}}},p_{b_{i_{1}}+1})\ldots(u_{b_{i_{2}}},p_{b_{i_{2}}-1},p_{b_{i_{2}}}).$

There are $\delta(\alpha)$ and $\delta(\beta)$ in $X_{n}^{*}$ such that
$w_{a_{i_{1}}+1}\ldots w_{a_{i_{2}}}$ is equivalent to $\alpha\delta(\alpha)$
and $u_{b_{i_{1}}+1}\ldots u_{b_{i_{2}}}$ is equivalent to
$\beta\delta(\beta)$. Using the facts that $\beta=\xi\alpha$,
$\nu_{i_{1}}=\nu(\alpha)_{i_{1}}\alpha=\nu(\beta)_{i_{1}}\beta$ and
$\nu_{i_{1}}\delta(\alpha)\alpha=\nu_{i_{1}}\delta(\beta)\beta=\nu_{i_{2}}$
(since $\alpha_{i_{2}}=\alpha_{i_{1}}=\alpha$). It follows that
$\delta(\beta)\xi=\delta(\alpha)$. Therefore,
$\alpha\delta(\alpha)=\alpha\delta(\beta)\xi$ and
$\beta\delta(\beta)=\xi\alpha\delta(\beta)$ are rotations of one another.

Observe that

$(w_{a_{i_{1}}+1},q_{a_{i_{1}}},q_{a_{i_{1}}+1})\ldots(w_{a_{i_{2}}},q_{a_{i_{2}}-1},q_{a_{i_{2}}})$

and

$(u_{b_{i_{1}}+1},p_{b_{i_{1}}},p_{b_{i_{1}}+1})\ldots(u_{b_{i_{2}}},p_{b_{i_{2}}-1},p_{b_{i_{2}}})$

are in fact circuits based at $q_{a_{i_{1}}}=q_{a_{i_{2}}}$ and
$p_{b_{i_{1}}}=p_{b_{i_{2}}}$ respectively. Moreover as $w_{a_{i_{1}}+1}\ldots
w_{a_{i_{2}}}$ is equivalent to $\alpha\delta(\alpha)$ and
$u_{b_{i_{1}}+1}\ldots u_{b_{i_{2}}}$ is equivalent to $\beta\delta(\beta)$,
we conclude, by the strong synchronizing condition, that
$(w_{a_{i_{1}}+1},q_{a_{i_{1}}},q_{a_{i_{1}}+1})\ldots(w_{a_{i_{2}}},q_{a_{i_{2}}-1},q_{a_{i_{2}}})$
is equal to a rotation of
$(u_{b_{i_{1}}+1},p_{b_{i_{1}}},p_{b_{i_{1}}+1})\ldots(u_{b_{i_{2}}},p_{b_{i_{2}}-1},p_{b_{i_{2}}})$.
This means there are $j_{1},j_{2}$, with $a_{i_{1}}\leq
j_{1},j_{2}<a_{i_{2}}$, such that
$(w_{{j_{1}}+1},q_{{j_{1}}},q_{{j_{1}}+1})=(u_{{j_{2}}+1},p_{{j_{2}}},p_{{j_{2}}+1})$
and the words $w_{1}w_{2}\ldots w_{{j_{1}}+1}$ and $u_{1}u_{2}\ldots
u_{{j_{2}}+1}$ are equivalent. However, the strong synchronizing condition
again implies that this happens only when

$(w_{1},q_{0},q_{1})(w_{2},q_{1},q_{2})\ldots(w_{j_{1}+1},q_{j_{1}-1},q_{j_{1}+1})$

and

$(u_{1},p_{0},p_{1})(u_{2},p_{1},p_{2})\ldots(u_{j_{2}+1},p_{j_{2}-1},p_{j_{2}+1})$

are the same path in $A$. For, otherwise, using the strongly connected
hypothesis and the existence of prime circuits in $A$ (Remark 4.2), we may
find a word $\varrho\in\pi_{A}^{\ast}$ such that

$(w_{1},q_{0},q_{1})(w_{2},q_{1},q_{2})\ldots(w_{j_{1}+1},q_{j_{1}-1},q_{j_{1}+1})\varrho$

and

$(u_{1},p_{0},p_{1})(u_{2},p_{1},p_{2})\ldots(u_{j_{2}+1},p_{j_{2}-1},p_{j_{2}+1})\varrho$

are circuits based at $q=p_{0}=q_{0}$ which are also prime words in
$\pi_{A}^{\ast}$. Remark 4.2 implies that the output of both of these circuits
is equivalent to a prime word in $X_{n}^{*}$. Furthermore, by construction,
the outputs of the two circuits are equivalent to the same word in
$X_{n}^{*}$. It thereofore follows that, as the circuits cannot be rotations
of one another, being prime, they must be equal. ∎

######  Corollary 4.6.

Let $A$ be a core strongly synchronizing non-deterministic automaton. Let
$q\in Q_{A}$. For any $x\in\mathrm{Domain}{(q)}$, there is a unique infinite
path

$(w_{1},q_{0}=q,q_{1})(w_{2},q_{1},q_{2})(w_{3},q_{2},q_{3})\ldots$

in $A$ and a non-decreasing sequence $i_{1}\leq i_{2}\leq
i_{3}\ldots\in\mathbb{N}$ with $\lim_{j\to\infty}i_{j}=\infty$ and
$w_{1}\ldots w_{i_{j}}\equiv x_{[1,i_{j}]}$ for all $j\in\mathbb{N}_{1}$.

###### Proof.

Since $x\in\mathrm{Domain}{(q)}$ such a sequence exists by definition. Suppose

$\displaystyle(w_{1},q_{0}=q,q_{1})(w_{2},q_{1},q_{2})(w_{3},q_{2},q_{3})\ldots$
(3) and
$\displaystyle(u_{1},p_{0}=q,p_{1})(u_{2},p_{1},p_{2})(u_{3},p_{2},p_{3})\ldots$
(4)

are two such sequences. We prove, by induction that they must be equal.

By Lemma 4.5 there is an $i_{1}\in\mathbb{N}_{1}$ such that

$(w_{1},q_{0},q_{1})\ldots(w_{i_{1}},q_{i_{1}-1},q_{i_{1}})=(u_{1},p_{0},p_{1})\ldots(u_{i_{1}},p_{i_{1}-1},p_{i_{1}})\ldots.$

Let $j_{1}\in\mathbb{N}_{1}$ be such that $w_{1}\ldots
w_{i_{1}}=x_{[1,j_{1}]}$. Let $x^{\prime}$ be defined by the equality
$x=x_{[1,j_{1}]}x^{\prime}$. Then it is clear that
$x^{\prime}\in\mathrm{Domain}{(p_{i_{1}})}$.

Replacing $q$ with $p_{i_{1}}$ and $x$ with $x^{\prime}$ we may thus repeat
the argument above with the infinite paths

$\displaystyle(w_{i_{1}+1},q_{i_{1}}=p_{i_{1}},q_{i_{1}+1})(w_{i_{1}+2},q_{i_{1}+1},q_{i_{1}+2})\ldots$
and
$\displaystyle(u_{i_{1}+1},p_{i_{1}}=q_{i_{1}},p_{i_{1}+1})(u_{i_{1}+2},p_{i_{1}+1},p_{i_{1}+2})\ldots.$

Inductively we conclude that the infinite paths 3 and 4 must be equal.

∎

In light of Corollary 4.6 above, we have the following definition. Let $T$ be
a strongly synchronizing transducer and $q$ a state of $T$. Let
$x\in\mathrm{Domain}{(q)}$ and let
$(w_{1},q_{0}=q,q_{1})(w_{2},q_{1},q_{2})(w_{3},q_{2},q_{3})\ldots$ be the
unique infinite path in $A$ with $w_{1}\ldots w_{i_{j}}\equiv x_{[1,i_{j}]}$,
for all $j\in\mathbb{N}$ and for a non-decreasing divergent sequence
$(i_{j})_{j\in\mathbb{N}}$ of natural numbers. Write $\lambda_{T}(x,q)$ for
the element $y\in X_{n}^{\omega}$ such that for any $j\in\mathbb{N}$,
$\lambda_{T}(w_{1},q_{0}=q,q_{1})\lambda_{T}(w_{2},q_{1},q_{2})\lambda_{T}(w_{3},q_{2},q_{3})\ldots\lambda_{T}(w_{j+1},q_{j},q_{j+1})$
is equivalent to a prefix of $y$. Write $\mathrm{Image}{(q)}$ for the set
$\\{\lambda_{T}(x,q)\mid x\in\mathrm{Domain}{(q)}\\}$.

######  Remark 4.7.

Let $T$ be a core and strongly synchronizing transducer. The map
$\lambda_{T}(\cdot,q):\mathrm{Domain}{(q)}\to\mathrm{Image}{(q)}$ is a well-
defined continuous and surjective map. If $T$ is bi-synchronizing then
$\lambda_{T}(\cdot,q)$ is a homeomorphism. This follows by applying Corollary
4.6 to the output automaton of $T$.

We have the following results.

######  Lemma 4.8.

Let $A$ be a core strongly synchronizing non-deterministic automaton. Then for
any state $q\in Q_{A}$, $\mathrm{Domain}{(q)}$ is clopen.

###### Proof.

It suffices to show that for $q\in Q_{T}$, there is a $\nu\in X_{n}$ such that
$U_{\nu}^{+}\subseteq\mathrm{Domain}{(q)}$.

To see why this suffices let $p\in Q_{A}$ be any state. Using the strong
connectivity of $A$, we may find a path
$\mathsf{w}=(w_{1},q=q_{0},q_{1})(w_{2},q_{1},q_{2})\ldots(w_{i},q_{i-1},p)$.
Write $\mu$ for the element of $X_{n}^{*}$ equivalent to $w_{1},w_{2},\ldots
w_{i}$ and note that we may chose the path $\mathsf{w}$ such that $\mu$ has
prefix $\nu$. Let $N$ be as in the statement of Lemma 4.5 and $\xi\in
X_{n}^{N}$ be a prefix of an element of $\mathrm{Domain}{(p)}$. Then,
$(\mu\xi)L_{q}$ has prefix $\mathsf{w}$. This follows as $\xi$ has length $N$,
and so if
$(\mu\xi)L_{q}=(w_{1},q=q_{0},q_{1})(w_{2},q_{1},q_{2})\ldots(w_{a},q_{a-1},q_{a})$
for some $a<i$, then, for $\delta$ the prefix of $\mu$ equivalent to
$w_{1}\ldots w_{a}$, $(\mu\xi-\delta)L_{q_{a}}=\varepsilon$ contradicting
Lemma 4.5. Thus, any element of $\mathrm{Domain}{(q)}$ with prefix $\mu\xi$ is
the output of an infinite path beginning with $\mathsf{w}$. Since
$U_{\mu}^{+}\subseteq\mathrm{Domain}{(q)}$, it follows that
$U_{\xi}^{+}\subseteq\mathrm{Domain}{(p)}$. Therefore, for $X(p)\subseteq
X_{n}^{N}$, the set of length $N$ prefixes elements of $\mathrm{Domain}{(p)}$,
$\mathrm{Domain}{(p)}=\bigcup_{\xi\in X(p)}U_{\xi}^{+}$ proving that
$\mathrm{Domain}{(p)}$ is clopen.

We now show that for $q\in Q_{A}$, $\mathrm{Domain}{(q)}$ contains a clopen
subset of $X_{n}^{\omega}$.

Once more using the strong connectivity of $A$, we may find a circuit
$\mathsf{w}\in\pi_{A}$ based at $q$. Let $w\in X_{n}^{+}$ be equivalent to the
concatenation of labels on the edges in the circuit. We may further assume,
since $T$ is strongly synchronizing, that $w$ is a prime word. Now, it is not
hard to see using the fact that $T$ is strongly synchronizing and has finitely
many states, that there is an $L\in\mathbb{N}$, such that for any state $p\in
Q_{A}$ and any path $(v_{1},p_{0}=p,p_{1})(v_{2},p_{1},p_{2})\ldots$ for which
$w^{L}$ is equivalent to a prefix of $v_{1}v_{2}\ldots$, there is minimal
$i_{1}\in\mathbb{N}$ and a maximal $i_{2}\in\mathbb{N}$ with
$(v_{i_{1}},p_{{i_{1}}-1},p_{{i_{1}}})\ldots(v_{i_{2}},p_{{i_{2}}-1},p_{{i_{2}}})$
a power of $\mathsf{w}$ and $v_{1}v_{2}\ldots v_{i_{2}}$ equivalent to
$w^{L}$.

Let $\delta\in X_{n}^{+}$ be any word such that $w\perp\delta$ . There is an
$l\in\mathbb{N}$ with $l>L$ such that $w^{l}\delta$ is a prime word. The
strong synchronizing condition means we can find a state $p\in Q_{A}$ and a
circuit $\mathsf{v}\in\pi_{A}$ based at $p$ whose label corresponds to the
word $w^{l}\delta$. By definition of $L$, it therefore follows there is a path
leaving $q$ with domain label containing a prefix equivalent to $w^{a}\delta$
for some $a<l$.

We observe that for any path $\mathsf{w}^{\prime}\in\pi_{A}^{\ast}$ beginning
at $q$ which does not have $\mathsf{w}$ as a prefix and whose domain label
contains a prefix equivalent to $w$, the maximal power of $w$ which is
equivalent to the domain label of the path $\mathsf{w}^{\prime}$ is strictly
less than $L$. This fact readily implies that for any word $\delta\in
X_{n}^{+}$ of length greater than $|w|$ and which does not contain $w$ as a
prefix, $w^{L}\delta$ is a prefix of an element of $\mathrm{Domain}{(q)}$.
Therefore, by induction, we see that
$U_{w^{L}}^{+}\subseteq\mathrm{Domain}{(q)}$. ∎

######  Remark 4.9.

Let $T$ be a core bisynchronizing non-deterministic transducer, then for any
state $q\in Q_{T}$, $\mathrm{Domain}{(q)}$ and $\mathrm{Image}{(q)}$ are
clopen.

######  Propostion 4.10.

Let $T$ be a core strongly synchronizing non-deterministic transducer. Then
there is a strongly synchronizing transducer $S$ with the following property.
Given $u\in X_{n}^{+}$ and writing

$(w_{1},p_{1},p_{2})(w_{2},p_{2},p_{3})\ldots(w_{m},p_{m},p_{m+1}=p_{m})\in\pi_{T}^{+}$

for the unique circuit (up to rotation) in $T$ such that $w_{1}\ldots w_{m}$
is equivalent to an element in $[u]_{\sim_{{\mathmbox{rot}}}}$, for $v\in
X_{n}^{+}$ such that
$v\equiv\lambda_{T}(w_{1},p_{1},p_{2})\ldots\lambda_{T}(w_{m},p_{m},p_{m+1})$,
we have,
$[v]_{\sim_{{\mathmbox{rot}}}}\equiv[\lambda_{S}(u,q_{u})]_{\sim_{{\mathmbox{rot}}}}$.

###### Proof.

We begin by constructing the transducer $S$ from $T$, we then argue that $S$
has the required properties.

Set $Q_{S}$ to be the set of all pairs $(w,q)$ in $X_{n}^{*}\times Q_{T}$
where $U^{+}_{w}\subseteq\mathrm{Domain}{(q)}$ and $(w)L_{q}=\varepsilon$.

We argue that $Q_{S}$ is finite.

Let $q\in Q_{T}$ and $x\in X_{n}^{*}$. Since $\mathrm{Domain}{(p)}$ is clopen
for any $p\in Q_{T}$, then for any such $p$, there is a minimal
$l\in\mathbb{N}$ and words $\mu_{1},\ldots,\mu_{r}\in X_{n}^{l}$ such that
$\bigcup_{1\leq i\leq r}U^{+}_{\mu_{i}}=\mathrm{Domain}{(p)}$. Furthermore, by
the non-degeneracy condition, there is a $j\in\mathbb{N}$, $j\geq 1$, such
that for any state $p\in Q_{T}$ and any path
$(w_{1},p,p_{1}),\ldots,(w_{j},p_{j-1},p_{j})$, the word $w_{1}\ldots w_{j}$
is equivalent to an element of $X_{n}^{+}$ of length at least $l$.

Suppose $(x,q,p)$ is an edge in $T$. Let $v,\nu\in X_{n}^{*}$ such that
$v\equiv x$ and $\nu\equiv w_{1}\ldots w_{j}$ where
$(w_{1},p,p_{1}),\ldots,(w_{j},p_{j-1},p_{j})$ is a path of length $j$
beginning at $p$. We note that $|\nu|\geq l$.

Suppose for a contradiction that $(v\nu)L_{q}$ is the empty word in
$\pi_{T}^{\ast}$. This means that there are elements
$y=y_{1},y_{2},\ldots,y_{m}\in X_{n}$, states $q_{1},q_{2},\ldots,q_{m}\in
Q_{T}$, such that
$(y_{1},q,q_{1}),(y_{2},q_{1},q_{2}),\ldots,(y_{m},q_{m-1},q_{m})$ is a path
beginning at $q$, $y_{1}y_{2}\ldots y_{m}$ has a prefix equivalent to $v\nu$
and $(y_{1},q,q_{1})\neq(x,q,p)$.

Using the fact that $T$ is strongly connected, we may find a circuit

$(y_{m+1},q_{m},q_{m+1}),\ldots,(y_{m+k},q_{m+k-1},q_{m+k}=q_{m}).$

Let $\delta\equiv y_{m+1}\ldots y_{m+k}$, noting that $\delta$ is non-empty by
the non-degenracy assumption. Then $\delta^{\omega}$ is an element of
$\mathrm{Domain}{(q_{m})}$.

Since $|\nu|\geq l$, then $U^{+}_{\nu}\subseteq\mathrm{Domain}{(p)}$ and
$\nu\delta^{\omega}$ is an element of $\mathrm{Domain}{(p)}$. Thus there is a
infinite path
$(w_{1}^{\prime},p,p_{1}^{\prime}),(w_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})\ldots$
such that $w_{1}^{\prime}w_{2}^{\prime}\ldots\equiv v\nu\delta^{\omega}$. By
the strong synchronizing condition, it must be the case that there is an
$N\in\mathbb{N}$ such that
$(w_{N}^{\prime},p_{N-1}^{\prime},p_{N}^{\prime})(w_{N+1}^{\prime},p_{N}^{\prime},p_{N+1}^{\prime})\ldots=((y_{m+1},q_{m},q_{m+1})\ldots(y_{m+k},q_{m+k-1},q_{m}))^{\omega}$.
This follows since by a compactness type argument, using the fact that $T$ has
finitely many states and $\delta$ is finite, there are $N,a\in\mathbb{N}$ such
that
$(w^{\prime}_{N},p^{\prime}_{N-1},p_{N}^{\prime})(w_{N+1}^{\prime},p_{N}^{\prime},p_{N+1}^{\prime})\ldots(w_{N+a+1}^{\prime},p_{N+a}^{\prime},p_{N+a}^{\prime})$,
$p_{N+a}^{\prime}=p_{N-1}^{\prime}$, is a circuit in $T$ and
$w^{\prime}_{N}w_{N+1}^{\prime}\ldots w_{N+a+1}^{\prime}$ is equivalent to an
element of $X_{n}^{*}$ in $[\delta^{b}]_{\sim_{{\mathmbox{rot}}}}$ for some
$b$.

Therefore there are $a,b\in\mathbb{N}$ such that

$(x,q,p)(w_{1}^{\prime},p,p_{1}^{\prime})(w_{2}^{\prime},p_{1}^{\prime},p_{2}^{\prime})\ldots(w_{N-1}^{\prime},p_{N-2}^{\prime},p_{N-1}^{\prime})((y_{m+1},q_{m},q_{m+1})\ldots(y_{m+k},q_{m+k-1},q_{m}))^{a}$

and

$(y,q,q_{1}),\ldots(y_{m},q_{m},q_{m+1})((y_{m+1},q_{m},q_{m+1})\ldots(y_{m+k},q_{m+k-1},q_{m}))^{b}$

are paths in $T$, and