# Synchronizing Dynamical Systems:
Shift Spaces and $K$-Theory

Andrew M. Stocker  Andrew M. Stocker, Department of Mathematics, University of
Colorado Boulder Campus Box 395, Boulder, CO 80309-0395, USA
<EMAIL_ADDRESS>
###### Abstract.

Building on previous work by the author and Robin Deeley, we give a thorough
presentation of the techniques developed for synchronizing dynamical systems
in the special case of synchronizing shift spaces. Following work of Thomsen,
we give a construction of the homoclinic and heteroclinic $C^{\ast}$-algebras
of a shift space in terms of Bratteli diagrams. Lastly we present several
specific examples which demonstrate these techniques. For the even shift we
give a complete computation of all the associated invariants. We also present
an example of a strictly non-sofic synchronizing shift. In particular we
discuss the rank of the $K$-theory of the homoclinic algebra of a shift space
and its implications. We also give a construction for producing from any
minimal shift a synchronizing shift whose set of non-synchronizing points is
exactly the original minimal shift.

This material is based upon work partially supported by the National Science
Foundation under Grant No. DMS 2000057.

## Introduction

In [6] we have outlined the basic theory of synchronizing dynamical systems
(or henceforth just “synchronizing systems”). The theory of synchronizing
systems is fundamentally based on techniques established in the study of Smale
spaces. Smale spaces are dynamical systems which are uniformly hyperbolic [15,
14, 20]. Synchronizing systems, however, are dynamical systems which are
hyperbolic almost everywhere. Hence almost all points in a synchronizing
system have local hyperbolic behavior, except that we allow for a
topologically small set of singular points. A precise definition can be found
in [6]. The term “synchronizing” is borrowed directly from the field of
symbolic dynamics where there is a notion of a synchronizing shift [8, 1]. Our
definition of synchronizing system generalizes this class of shift spaces, see
Lemma 2.1. Synchronizing shifts are thus an important example of synchronizing
systems — in fact they are the focus of the current paper.

Expansive dynamical systems are topological dynamical systems which exhibit
sensitivity to initial conditions. Concretely, we say that a dynamical system
$(X,\varphi)$ (i.e. $X$ is a compact metric space and $\varphi:X\to X$ is a
homeomorphism) is _expansive_ if there exists a constant $\varepsilon_{X}>0$
such that $d(\varphi^{n}(x),\varphi^{n}(y))\leq\varepsilon_{X}$ for all
$n\in\mathbb{Z}$ implies $x=y$. Shift spaces are of crucial importance in the
study of expansive systems. In light of the fact that every expansive system
is a factor of a shift space [22], there is a direct connection between the
combinatorial nature of shift spaces and the dynamics of expansive systems.
This further justifies the current paper’s focus on shift spaces in
particular. Additionally, we will find that for shift spaces we can much more
explicitly compute the invariants presented in [6].

A synchronizing shift is an irreducible shift space $X$ which admits a word
$w\in\mathcal{L}(X)$ with the following property: if $u,v\in\mathcal{L}(X)$
are such that $uw\in\mathcal{L}(X)$ and $wv\in\mathcal{L}(X)$, then
$uwv\in\mathcal{L}(X)$. An arbitrary shift space may not even have a
synchronizing word, and not all words in a synchronizing shift have this
property (a word with this property is itself called synchronizing). A
synchronizing shift in which all words are (eventually) synchronizing is a
shift of finite type, see [4, Theorem 2.1.8]. However the class of
synchronizing shifts contains many shift spaces that are not shifts of finite
type. Most importantly every irreducible sofic shift is synchronizing, see [6,
Corollary 3.11]. However, even beyond the irreducible sofic shifts there are
many interesting synchronizing shifts which are strictly non-sofic, see
Section 7.2 and Section 9 for examples.

We will now draw a connection between the concept of a synchronizing word and
a point in a shift space having local hyperbolic behavior. Suppose $X$ is a
synchronizing shift space and $x\in X$, $N\geq 0$ are such that $x_{[-N,N]}$
is a synchronizing word. If $y^{-}$ and $z^{+}$ are any left infinite and
right infinite rays that may be concatenated to the left and right of
$x_{[-N,N]}$ (respectively), then $x^{\prime}=y^{-}x_{[-N,N]}z^{+}$ is a valid
element of $X$ due to $x_{[-N,N]}$ being synchronizing. Hence the set of such
left/right-infinite rays $\\{(y^{-},z^{+})\\}$ is a Cartesian product. In fact
this set corresponds to a set of pairs $(y,z)$ in $X$ for which $z$ is stably
equivalent to $x$, in the sense that for some $N\in\mathbb{Z}$ we have
$z_{n}=x_{n}$ for all $n\geq N$; and $y$ is unstably equivalent to $x$ in the
symmetric sense. By the above, the set of such $(y,z)$ is also a Cartesian
product. Stable and unstable equivalence are a dynamical notion, and it is in
this sense that the dynamical behavior of $(X,\sigma)$ near $x$ can be seen to
be hyperbolic. This connection is spelled out explicitly in Section 2.

With techniques developed here and in [6], synchronizing systems represent a
significant broadening of the types of expansive dynamical systems for which
we have tools to study. In [21], Thomsen has shown that a $C^{\ast}$-algebra
$A(X,\varphi)$ called the _homoclinic algebra_ can be associated to any
expansive dynamical system. See Section 4.1 for a description of this algebra
when $X$ is a shift space — this construction is entirely due to Thomsen. In
the case when $X$ is a synchronizing system however, we have shown in [6] that
there is an ideal $\mathcal{I}_{\text{sync}}(X,\varphi)\subseteq A(X,\phi)$
determined by the set of synchronizing points in $X$. Hence the fundamental
structure of the homoclinic algebra of a synchronizing system can be
understood in terms of the following short exact sequence.

$0\longrightarrow\mathcal{I}_{\text{sync}}(X,\varphi)\longrightarrow
A(X,\varphi)\longrightarrow
A(X,\varphi)/\mathcal{I}_{\text{sync}}(X,\varphi)\longrightarrow 0$

When $X$ is a synchronizing shift, the groupoid $G^{\text{lc}}(X,\sigma)$ used
to build the homoclinic algebra is amenable and so we obtain that

$A(X,\sigma)/\mathcal{I}_{\text{sync}}(X,\sigma)\cong
C^{\ast}\left(G^{\text{lc}}(X,\sigma)|_{X_{\text{non-sync}}}\right)$

in the above short exact sequence. Note that in general this quotient is not
the same as the homoclinic algebra of the subshift of non-synchronizing points
$X_{\text{non-sync}}$ — see Section 8 for an explicit example.

Irreducible finitely presented systems, introduced by Fried in [9], are shown
to also be synchronizing systems in [6]. The shift spaces that are finitely
presented systems are exactly the sofic shifts introduced by Weiss in [23].
Hence an irreducible sofic shift is synchronizing. However, when a sofic shift
is mixing we may understand the structure of
$\mathcal{I}_{\text{sync}}(X,\sigma)$ in a very explicit way as follows. In
[21], Thomsen introduced the heteroclinic algebras for an expansive dynamical
system in which periodic points are dense. A main result of [6] is that
synchronizing systems, and thus also irreducible finitely presented systems,
have a dense set of periodic points. However, Thomsen’s heteroclinic algebras
are built using the set of all periodic points in $X$, and in a synchronizing
system the synchronizing and non-synchronizing periodic points behave very
differently. In [14], Putnam and Spielberg construct the stable and unstable
algebras of a Smale space by fixing a periodic point (or finite set of
periodic orbits). They then show that up to Morita equivalence this choice
does not matter. Inspired by this, we modify Thomsen’s heteroclinic algebras
so that we instead fix a single _synchronizing_ periodic point — or more
generally a finite set of them. We have also shown that this choice does not
matter up to Morita equivalence, see [6, Theorem 5.5]. Hence we call this
modified construction collectively the heteroclinic synchronizing algebras of
$(X,\varphi)$. More specifically we associate to a synchronizing system the
stable synchronizing algebra $S(X,\varphi,p)$ and unstable synchronizing
algebra $U(X,\varphi,p)$ where $p\in X$ is a synchronizing periodic point. A
fundamental result in [6] is that when $(X,\varphi)$ is a mixing finitely
presented system, we have the Morita equivalence

$S(X,\varphi,p)\otimes
U(X,\varphi,p)\sim_{\text{M.E.}}\mathcal{I}_{\text{sync}}(X,\varphi)\,.$

Hence this Morita equivalence also holds for mixing sofic shifts, of which the
even shift is a prime example. In Section 5 we show how this Morita
equivalence can be seen explicitly in our computations.

Although synchronizing shift spaces are a special case of the synchronizing
systems discussed in [6], we aim to make this paper as self-contained as
possible. In Section 1 we will give an introduction to shift spaces. We will
also introduce shifts of finite type and sofic shifts. Section 2 will be
specifically focused on synchronizing shifts. In this section we show that our
definition of synchronizing given in [6] generalizes the class of
synchronizing shifts.

In Section 3 we discuss the equivalence relations defined in [6] in the
context of shift spaces. Then in Section 4 we show how these equivalence
relations can be produced inductively using Bratteli diagrams. From these
Bratteli diagrams we define several different $C^{\ast}$-algebras. The
$K$-theory of these $C^{\ast}$-algebras are conjugacy invariants of the
underlying shift spaces [21]. In the examples to follow we show how these
$K$-theory groups contain information about the asymptotic behavior of shift
spaces. We also discuss briefly the short exact sequence determined by the
synchronizing ideal, and additionally a Morita equivalence which relates these
$C^{\ast}$-algebras.

In Section 5 through Section 9 we will be presenting several examples which
demonstrate some of the possible behavior that can be observed in a
synchronizing shift. These examples will demonstrate that the techniques of
[6] that have been specialized to shift spaces in the current paper. We will
give examples for which

  1. (i)

the set of non-synchronizing points is a single point (Section 5),

  2. (ii)

the set of non-synchronizing points is infinite (Section 6),

  3. (iii)

the rank of the $K$-theory of the homoclinic algebra is infinite (Section 7),

  4. (iv)

the quotient algebra can be described intrinsically (Section 8)

  5. (v)

and lastly an example where the set of non-synchronizing points is a minimal
shift space (Section 9).

The even shift, denoted $X_{\text{even}}$, is presented in Section 5. This is
intended to be a complete example where all invariants are computed. We remark
that Thomsen has computed the Bratteli diagram for the homoclinic algebra of
the even shift in [21], although our computation is much more explicit. The
even shift has a single non-synchronizing point, and thus we obtain the short
exact sequence

$0\longrightarrow\mathcal{I}_{\text{sync}}(X_{\text{even}},\sigma)\longrightarrow
A(X_{\text{even}},\sigma)\longrightarrow\mathbb{C}\longrightarrow 0\,.$

We also discuss how the failure of the even shift to be a shift of finite type
can be seen through the fact that the homoclinic algebra of the even shift is
not Morita equivalent to the tensor product of its heteroclinic algebras.

However it is not the case the set of non-synchronizing points must be finite
or even countable — such an example is demonstrated in the case of the charge-
constrained shift in Section 6. Also note for the shift space in Section 8,
the subshift of non-synchronizing points is exactly the full 2-shift.

The significance of (iii) is that it is known that $K$-theory of the
homoclinic algebra of a sofic shift space is of finite rank, see Section 7.2.
Hence, the rank of the $K$-theory of the homoclinic algebra of a shift space
$X$ may be seen as obstructing $X$ belonging to the class of sofic shifts. In
Section 7, we give a thorough examination of an example of a synchronizing
shift for which the rank of the $K$-theory of the homoclinic algebra is
infinite. This involves using infinite labeled graph representations and
relating the rank of the $K$-theory of the homoclinic algebra to paths on
these graphs. The author suspects that a similar technique could be use to
prove that the $K$-theory of the homoclinic algebra is infinite rank for other
synchronizing shifts which have the following property: there exists a finite
set $F\subseteq\mathcal{L}_{\text{sync}}(X)$ such that $w\in\mathcal{L}(X)$ is
synchronizing if and only if $u\sqsubseteq w$ for some $u\in F$.

One may wonder what kinds of shift spaces may appear as the subshift of non-
synchronizing points in a synchronizing shift. We have seen an example where
the subshift of non-synchronizing points is the full 2-shift, and the shift
space presented in Section 7 also has a shift of finite type as its subshift
of non-synchronizing points. Unfortunately, there does not appear to be any
sort of constraint on the type of shifts that can appear. In Section 9 we show
that, given any minimal shift $M$, we can construct a synchronizing shift
whose set of non-synchronizing points is exactly $M$.

## Acknowledgments

I would like thank Ian Putnam for his many helpful comments on my doctoral
work which resulted in this paper, and Robin Deeley for his advising and
collaboration. This material is based upon work partially supported by the
National Science Foundation under Grant No. DMS 2000057.

##  1\. Shift Spaces

Let $\mathcal{A}$ be a finite set of symbols which we will call an _alphabet_.
Then the space

$\mathcal{A}^{\mathbb{Z}}=\\{\ldots x_{-2}x_{-1}.x_{0}x_{1}x_{2}\ldots\mid
x_{i}\in\mathcal{A}\text{ for all }i\in\mathbb{Z}\\}$

with the product topology is a compact topological space which is also totally
disconnected. We will typically write a sequence with a decimal point to
indicate the zero-th index. Let
$\sigma:\mathcal{A}^{\mathbb{Z}}\to\mathcal{A}^{\mathbb{Z}}$ be the map
defined by $\sigma(x)_{i}=x_{i+1}$. This is called the _shift map_. It is a
homeomorphism of $\mathcal{A}^{\mathbb{Z}}$ [13].

######  Definition 1.1.

A _shift space_ is a dynamical system $(X,\sigma)$ where $\sigma$ is the shift
map and $X\subseteq\mathcal{A}^{\mathbb{Z}}$ is a closed subspace of
$\mathcal{A}^{\mathbb{Z}}$ which is invariant under $\sigma$.

Since the dynamical map on a shift space is always $\sigma$ (implicitly
restricted to $X$) we will often denote a shift space $(X,\sigma)$ as just
$X$. For a more detailed treatment of shift spaces, see [4].

It will be useful for us to consider all the words of finite length (including
the empty word) that appear in elements of a shift space. Let the _language_
of $X$, denoted $\mathcal{L}(X)$, be the collection of all finite strings that
appear in elements of $X$, that is, $w\in\mathcal{L}(X)$ if and only if
$w=x_{k}x_{k+1}\cdots x_{k+n}$ for some $x\in X$ — we denote this
$w\sqsubseteq x$. We will also often denote the word $x_{i}x_{i+1}\cdots
x_{j}$ as $x_{[i,j]}$ for $-\infty<i\leq j<\infty$, or $x_{[i,j)}$ for the
word $x_{i}x_{i+1}\cdots x_{j-1}$ for $-\infty<i<j\leq\infty$ (likewise for
$x_{(i,j]}$). Additionally we will also denote the length of a word $w$ as
$|w|$. Lastly, we will write the set of words of length $n$ appearing in
elements of $X$ as $\mathcal{L}_{n}(X)$, that is

$\mathcal{L}_{n}(X)=\mathcal{L}(X)\cap\mathcal{A}^{n}=\\{w\in\mathcal{L}(X)\mid|w|=n\\}\,.$

######  Example 1.1.

For an example of what $\mathcal{L}(X)$ looks like we can consider the _full
2-shift_ , which is defined as the shift space
$X=\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}$. Then
$\displaystyle\mathcal{L}(X)=\bigcup_{n\geq 0}\\{\mathtt{0},\mathtt{1}\\}^{n}$
which is the set of all finite binary words.

The topology on $X$ is generated by what are called cylinder sets. A _cylinder
set_ is a set of the form

$C(w)=\\{x\in X\mid x_{[-n,n]}=w\\}$

for $w\in\mathcal{L}_{2n+1}(X)$. Note that these are clopen sets in the
topology on $X$. Hence if $x\in X$ then the cylinder sets $C(x_{[-n,n]})$ are
neighborhoods of $x$ for all $n\geq 0$. Furthermore, the topology on a shift
space is given by the following metric:

$d(x,y)=\,\inf_{n\geq 1}\left\\{2^{-|n|}\,\middle|\,x_{i}=y_{i}\text{ for all
}|i|<n\right\\}$

when $x_{0}=y_{0}$, and $d(x,y)=1$ otherwise.

In fact it is not too hard to see that shift spaces are also expansive. The
proof is as follows, let $X$ be a shift space and fix $\varepsilon_{X}=1$.
Observe that for two distinct points $x,y\in X$ there is some $n\in\mathbb{Z}$
such that $x_{n}\neq y_{n}$, meaning $d(\sigma^{n}(x),\sigma^{n}(y))=1$. This
shows that $\varepsilon_{X}=1$ is an expansiveness constant for any shift
space assuming we are using the above metric.

######  Definition 1.2.

A shift space $X$ is called _irreducible_ if for each ordered pair
$w,v\in\mathcal{L}(X)$, there is a $u\in\mathcal{L}(X)$ such that
$wuv\in\mathcal{L}(X)$.

######  Definition 1.3.

A shift space $X$ is called _mixing_ if each each $w,v\in\mathcal{L}(X)$ there
is an $N$ such that for each $n\geq N$ there exists $u\in\mathcal{L}_{n}(X)$
such that $wuv\in\mathcal{L}(X)$.

It is well known that the above definition of irreducibility agrees with the
notion of irreducibility for topological dynamical systems.

###  1.1. Shifts of Finite Type

Let $\mathcal{A}$ be alphabet as defined above, and let
$F\subseteq\mathcal{L}(\mathcal{A}^{\mathbb{Z}})$ be a finite set of words in
$\mathcal{A}$ which we call a set of _forbidden words_. Then let
$X_{F}\subseteq\mathcal{A}^{\mathbb{Z}}$ be the set

$X_{F}=\\{x\in\mathcal{A}^{\mathbb{Z}}\mid w\not\sqsubseteq x\text{ for all
}w\in F\\}\,.$

Note that $X_{F}$ is a shift invariant subset of $\mathcal{A}^{\mathbb{Z}}$. A
shift space $X_{F}$ constructed in this way is called a _shift of finite type
(SFT)_ , see [4] for more details and an introduction to SFTs.

A useful way to construct SFTs is as follows. Let $G=(V,E)$ be a finite
directed graph, then let $X_{G}$ be the space of all bi-infinite paths on $G$
which we topologize as subspace of $E^{\mathbb{Z}}$ with the product topology.
Let us also denote as $r,s:E\to V$ the functions which send each edge on $G$
to its range and source vertex respectively. Then $X_{G}$, which we call the
_edge shift_ of $G$, is a shift of finite type since we must only forbid words
of the form $F=\\{ef\mid e,f\in E\text{ and }r(e)\neq s(f)\\}$, which is a
finite subset of $\mathcal{L}(E^{\mathbb{Z}})$.

Besides this being a useful construction, it is actually the case that any SFT
is conjugate to the edge shift of some graph $G$. Let $X_{F}$ be a SFT, then
since $F$ is a finite set there is an $N\geq 1$ such that $|w|\leq N$ for all
$w\in F$. We may then construct a graph $G=(V,E)$ by letting
$V=\mathcal{L}_{N-1}(X_{F})$, $E=\mathcal{L}_{N}(X_{F})$,
$r(e)=e_{2}e_{3}\cdots e_{N}$, and $s(e)=e_{1}e_{2}\cdots e_{N-1}$. Such a
graph $G$ is called a _presentation_ of $X_{F}$ and it is not necessarily
unique. By a result in [4, Section 2.3], $X_{F}$ is conjugate to $X_{G}$.

######  Example 1.2.

For example, every _full $n$-shift_, that is the shift space
$X_{n}=\\{\mathtt{0},\mathtt{1},\dots,\mathtt{n-1}\\}^{\mathbb{Z}}$, is a
shift of finite type. The full $n$-shift can be built from a graph with a
single vertex and $n$ edges.

######  Example 1.3.

Consider the shift space
$X\subseteq\\{\mathtt{a},\mathtt{e},\mathtt{f}\\}^{\mathbb{Z}}$ given by the
following graph $G$.

$v$$w$$\mathtt{a}$$\mathtt{e}$$\mathtt{f}$

This is a shift space called the _golden mean shift_. It is conjugate to the
shift of finite type $X_{F}\subseteq\\{\mathtt{0},\mathtt{1}\\}^{\mathbb{Z}}$
with the set of forbidden words $F=\\{\mathtt{11}\\}$. To see this observe
that if we construct the edge shift for $X_{F}$ with $N=2$, we obtain the
above graph with the labeling $\mathtt{a}=\mathtt{00}$,
$\mathtt{e}=\mathtt{01}$, and $\mathtt{f}=\mathtt{10}$ — see [4, Section 2.3]
for more details.

###  1.2. Sofic Shifts

Similar to shifts of finite type, sofic shifts are constructed from a graph
presentation except now we will consider graphs with labeled edges. Let
$G=(V,E)$ be a finite directed graph as before and let $\pi:E\to\mathcal{A}$
be a function which assigns to each edge $e\in E$ a label
$\pi(e)\in\mathcal{A}$. The function $\pi$ extends to a continuous function
$\pi:X_{G}\to\mathcal{A}^{\mathbb{Z}}$ where $X_{G}$ is the SFT constructed
from the unlabeled graph $G$. Let $X$ denote the image of $X_{G}$ under $\pi$,
then $\pi:X_{G}\to X$ is a factor map from $(X_{G},\sigma)$ to $(X,\sigma)$.
The function $\pi$ also extends to a function
$\pi:\mathcal{L}_{n}(X_{G})\to\mathcal{L}_{n}(X)$ which assigns to each finite
path in $G$ the word

$\pi(e_{1}e_{2}\cdots e_{n})=\pi(e_{1})\pi(e_{2})\cdots\pi(e_{n})$

in $\mathcal{L}(X)$. We say that a path $p\in\mathcal{L}_{n}(X_{G})$
_represents_ a word $w\in X$ if $\pi(p)=w$. Shift spaces constructed in this
way are called _sofic shifts_. Note that every shift of finite type is also a
sofic shift. Sofic shifts can be succinctly characterized as those shift
spaces that are factors of SFTs [4, Section 3.1].

######  Example 1.4.

A running example in this paper will be the _even shift_ , which is the sofic
shift space in the alphabet $\\{\mathtt{0},\mathtt{1}\\}$ whose elements do
not contain any of the finite words in the set
$F=\\{\mathtt{10}^{2k+1}\mathtt{1}\mid k\geq 0\\}$. That is to say that the
elements of the even shift are infinite binary sequences which have an even
number of consecutive zeros between any two ones. We will denote the even
shift as $X_{\text{even}}$. We can see that the even shift is not a shift
finite type since there is no upper bound on the size of the words that we
must forbid. More precisely, the countable set $F$ is a minimal set of
forbidden words for $X_{\text{even}}$. However, the even shift is indeed sofic
since it admits the following graph presentation.

$\mathtt{1}$$\mathtt{0}$$\mathtt{0}$

In this case, the edge shift $X_{G}$ coming the unlabeled graph above is
exactly the golden mean shift discussed in Example 1.3. In other words, the
even shift is a factor of the golden mean shift.

It is important to note that the factor map $\pi:X_{G}\to X$ may not be
injective. For example in the even shift there are two elements of $X_{G}$
that get mapped to the point
$\overline{\mathtt{0}}=\dots\mathtt{00.000}\dots$. However in this case this
is the only such point since as soon there is a $\mathtt{1}$ in a sequence
$x\in X$, we know exactly which element in $X_{G}$ must correspond to it. This
follows from the fact that there is only one vertex with an arrow labeled
$\mathtt{1}$ pointing to it. Hence $\pi$ is injective on almost all points in
$X_{G}$ except the two points that get mapped to $\overline{\mathtt{0}}$.

##  2\. Synchronizing Shifts

In the following section suppose $(X,\sigma)$ be a shift space.

######  Definition 2.1.

Let $X$ be a shift space and $w\in\mathcal{L}(X)$, then $w$ is called
_synchronizing_ if, for any two words $u,v\in\mathcal{L}(X)$,
$uw\in\mathcal{L}(X)$ and $wv\in\mathcal{L}(X)$ then $uwv\in\mathcal{L}(X)$.
An element $x\in X$ is called _synchronizing_ if it contains a synchronizing
word. A shift space $X$ is called _synchronizing_ if it is irreducible and
contains at least one synchronizing element (or, equivalently, if
$\mathcal{L}(X)$ contains a synchronizing word).

The concept of synchronizing for shift spaces can be found in the symbolic
dynamics literature in various forms. In [6] we have generalized this
definition for expansive topological dynamical systems. The above definition
in particular can be found in [8, 1]. In the literature synchronizing words
have also been called “intrinsically synchronizing” [4], “magic” [18], or
“finitary” [10].

######  Example 2.1.

For the even shift (Example 1.4), a word is synchronizing if and only if it
contains a $\mathtt{1}$. This is because the context of a word $w$ in the even
shift only depends on the parity of the number of zeros on the left or right
side of $w$, except in the special case when $w=\mathtt{0}^{k}$. In fact, the
point of all zeros, $\overline{\mathtt{0}}=\ldots\mathtt{00.000}\ldots$, is
the only non-synchronizing point in the even shift. In particular, the even
shift is a synchronizing shift space. To show it is irreducible, it is easy to
show that arbitrary $w,v\in\mathcal{L}(X)$ can be glued together with
$u=\mathtt{0}^{k}$ ensuring the parity of $k$ produces a valid word in the
even shift.

We remark that all irreducible sofic shifts are indeed synchronizing, see [6,
Corollary 3.11].

We will now describe the connection between synchronizing element of a shift
space in the sense of Definition 2.1 and the definition of synchronizing given
in [6, Definition 3.2].

######  Definition 2.2.

Let $X$ be a shift space and $w\in\mathcal{L}(X)$. The set

$E(w)=\\{(a,b)\in\mathcal{L}(X)\times\mathcal{L}(X)\mid
awb\in\mathcal{L}(X)\\}$

is called the _context_ of $w$. Note that for any $w,v\in\mathcal{L}(X)$ with
$E(w)=E(v)$ and $(a,b)\in E(w)$, we have $E(awb)=E(avb)$.

Alternatively, we can see that $w$ is synchronizing if it is the case that

$E\left(w\right)=A\times B$

where $A,B\subseteq\mathcal{L}(X)$ — this is simply a reformulation of the
definition. Note also that if $w$ is synchronizing then any word containing
$w$ is also synchronizing.

Consider $X$ the full $n$-shift. Define the _local stable and unstable_ sets
as (respectively)

$\displaystyle X^{\text{s}}(x,N)$ $\displaystyle=\\{y\in X\mid
y_{n}=x_{n}\,\forall n\geq N\\}\text{ , and }$ $\displaystyle
X^{\text{u}}(x,N)$ $\displaystyle=\\{y\in X\mid y_{n}=x_{n}\,\forall
n\leq-N\\}\,.$

The bracket map in [6, Definition 2.3], $[-,-]:X^{\text{u}}(x,N)\times
X^{\text{s}}(x,N)\to C\left(x_{[-N,N]}\right)$, is then given by

$([y,z])_{n}=\begin{cases}y_{n}&n>N\\\ x_{n}=y_{n}=z_{n}&|n|\leq N\\\
z_{n}&n<-N\end{cases}\,.$

The bracket map is always defined when $X$ is the full $n$-shift. However if
we restrict the bracket map to an arbitrary shift space $X$, the bracket map
may not be defined in general. We now state [6, Definition 3.2] in the case of
shift spaces.

######  Definition 2.3.

Suppose $X$ is an irreducible shift space. Then $x\in X$ is called
_synchronizing_ if there exists $N\geq 0$ such that $[-,-]$ is defined and is
a homeomorphism.

######  Lemma 2.1.

For shift spaces, Definition 2.3 agrees with Definition 2.1.

###### Proof.

If a point $x\in X$ is synchronizing in the sense of Definition 2.3, then
there is a cylinder set $C(x_{[-N,N]})$ such that the bracket map is defined
as above. It then follows that $E(x_{[-N,N]})$ is a Cartesian product and
hence the word $x_{[-N,N]}$ is synchronizing.

If $X$ contains a synchronizing point in the sense of Definition 2.1, then
there is an $N$ such that $x_{[-N,N]}$ is a synchronizing word. This implies
that $E(x_{[-N,N]})$ is a Cartesian product and hence the bracket map $[-,-]$
is defined and is indeed a homeomorphism. ∎

Hence synchronizing shifts are synchronizing dynamical systems in the sense of
[6]. We will write $X$ as a disjoint union of its synchronizing and non-
synchronizing points:

$X=X_{\text{sync}}\sqcup X_{\text{non-sync}}$

Note that if $X$ is a synchronizing shift then the $X_{\text{non-sync}}$ is
closed and shift invariant [6, Lemma 3.5]. Hence $X_{\text{non-sync}}$ is a
shift space which is determined by the set of non-synchronizing words (on this
last point, see [4]).

##  3\. Local Conjugacy

Local conjugacy is an equivalence relation which relates the local asymptotic
behavior of elements in a dynamical system. Thomsen defined local conjugacy
for expansive dynamical systems in [21]. In [6] we show that the property of
being synchronizing is invariant under local conjugacy [6, Proposition 4.6].
In the following, we will be using the definitions given in [6, Section 4]. We
review the definitions here, which are mainly due to Thomsen. These
equivalence relations are stated in terms of the topology on a shift space,
but we will show that there are equivalent characterizations in terms of the
language of a shift space.

######  Definition 3.1.

Let $X$ be a shift space. We say that two points $x,y\in X$ are _locally
conjugate_ , denoted $x\sim_{\text{lc}}y$, if there exist two open
neighborhoods $U$ and $V$ of $x$ and $y$ respectively, and a homeomorphism
$\gamma:U\to V$ such that $\gamma(x)=y$ and

$\lim_{n\to\pm\infty}\sup_{z\in
U}\,d(\sigma^{n}(z),\sigma^{n}(\gamma(z)))=0\,.$

######  Definition 3.2.

Let $X$ be a shift space with $x,y\in X$. Suppose $N,N^{\prime}\geq 0$ and
$\gamma:X^{\text{u}}(x,N)\to X^{\text{u}}(y,N^{\prime})$ is a homeomorphism
onto its image such that $\gamma(x)=y$ and

$\lim_{n\to\infty}\sup_{z\in U}d(\sigma^{n}(z),\sigma^{n}(\gamma(z)))=0\,.$

Then $\gamma$ is a called a _stable local conjugacy_ and we say that
$x\sim_{\text{lcs}}y$.

######  Definition 3.3.

Let $X$ be a shift space with $x,y\in X$. Suppose $N,N^{\prime}\geq 0$ and
$\gamma:X^{\text{s}}(x,N)\to X^{\text{s}}(y,N^{\prime})$ is a homeomorphism
onto its image such that $\gamma(x)=y$ and

$\lim_{n\to\infty}\sup_{z\in U}d(\sigma^{-n}(z),\sigma^{-n}(\gamma(z)))=0\,.$

Then $\gamma$ is a called an _unstable local conjugacy_ and we say that
$x\sim_{\text{lcu}}y$.

Let $X$ be a shift space and $x,y\in X$, then we will also refer to the
following equivalence relations.

  * •

$x\sim_{\text{s}}y$ if and only if there exists $N\in\mathbb{Z}$ such that
$x_{n}=y_{n}$ for all $n\geq N$.

  * •

$x\sim_{\text{u}}y$ if and only if there exists $N\in\mathbb{Z}$ such that
$x_{n}=y_{n}$ for all $n\leq N$.

  * •

$x\sim_{\text{h}}y$ if and only if there exists $N\geq 0$ such that
$x_{n}=y_{n}$ for all $n\geq N$ and $n\leq-N$.

Note that clearly $x\sim_{\text{lc}}y$ implies $x\sim_{\text{h}}y$ for any
expansive dynamical system. However the converse is not true, see Example 3.1.
The following result from [21] gives necessary and sufficient conditions for
$x\sim_{\text{lc}}y$ in a shift space.

######  Lemma 3.1.

If $(X,\sigma)$ is a shift space, then two points $x,y\in X$ are locally
conjugate if and only if there is an $N$ such that $x_{n}=y_{n}$ for all
$|n|>N$ and $E\left(x_{[-N,N]}\right)=E\left(y_{[-N,N]}\right)$. If the latter
is true, we can construct a local conjugacy
$\left(C\left(x_{[-N,N]}\right),C\left(y_{[-N,N]}\right),\gamma\right)$ from
$x$ to $y$ where $\gamma$ is defined by

$\gamma(z)_{n}=\begin{cases}z_{n}&|n|>N\\\ y_{n}&|z|\leq N\end{cases}\,.$

######  Example 3.1.

Here we give a counterexample, due to Thomsen [21, Remark 1.13], to the
statement $x\sim_{\text{h}}y$ implies $x\sim_{\text{lc}}y$. Consider the even
shift as in Example 1.4. Note that since in a shift space $x\sim_{\text{h}}y$
implies $x_{n}=y_{n}$ for all $|n|\geq N$ for some $N$, the sequences
$x=\ldots\mathtt{00.000}\ldots$ and $y=\ldots\mathtt{00.100}\ldots$ are
homoclinic in the even shift. However, observe that $(\mathtt{1},\mathtt{0})$
is in $E\left(\mathtt{0}^{4k-1}\right)$ but not in
$E\left(\mathtt{0}^{2k-1}\mathtt{10}^{2k-1}\right)$ for all $k\geq 1$, so
although $x$ is homoclinic to $y$ they cannot be locally conjugate. This can
also be readily seen from the fact that $y$ is synchronizing but $x$ is not,
and any point locally conjugate to $y$ must also be synchronizing.

###  3.1. Stable/Unstable Local Conjugacy

We must first introduce a definition similar to Definition 2.2 except we now
specialize to either the left or the right side of a word.

######  Definition 3.4.

Let $X$ be a shift space and $w\in\mathcal{L}(X)$. Then we define the sets

$\displaystyle E^{-}(w)$ $\displaystyle=\\{a\in\mathcal{L}(X)\mid
aw\in\mathcal{L}(X)\\}\text{ , and }$ $\displaystyle E^{+}(w)$
$\displaystyle=\\{b\in\mathcal{L}(X)\mid wb\in\mathcal{L}(X)\\}$

called the _left context_ and _right context_ of $w$, respectively.

There is an important caveat to the above definition that we must grapple
with. It is not necessarily the case for every synchronizing shift space that
the set of words that can be appended to the left-infinite ray
$x_{(-\infty,0]}$, i.e. the _follower set_ of $x_{(-\infty,0]}$, is the same
as $x_{[-N,0]}$ for any $N\geq 0$. For example, in the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift (see Section 7), one cannot append the
word $\mathtt{b}^{k}\mathtt{a}$ to the right of the left-infinity ray
$...\mathtt{aaa}$ for any $k\geq 1$, and yet the words $\mathtt{a}^{k}$ and
$\mathtt{b}^{k}\mathtt{a}$ can always be concatenated.

However, consider the case where $X$ is a synchronizing shift space and $x\in
X_{\text{sync}}$ with $N$ such that $x_{[-N,N]}$ is a synchronizing word. Then
it is the case that follower set of $x_{(-\infty,N]}$ is the same as
$E^{+}\left(x_{[-N,N]}\right)$. To see this observe that for any $b\in
E^{+}\left(x_{[-N,N]}\right)$, we have $x_{[-M,-N-1]}x_{[-N,N]}b$ is a valid
word in $X$ for any $M>N$ since $x_{[-N,N]}$ is synchronizing.

This motivates the following lemma. We remind the reader that in Lemma 3.2
below we are referring to the stable and unstable local conjugacy relations as
defined in [6, Section 4].

######  Lemma 3.2.

Suppose $(X,\sigma)$ is a synchronizing shift space with $x,y\in
X_{\text{sync}}$. Then the following are true.

  1. (i)

$x\sim_{\text{lcs}}y$ if and only if there exists $N\geq 0$ such that both
$x_{[-N,N]}$ and $y_{[-N,N]}$ are synchronizing words, $x_{n}=y_{n}$ for all
$n>N$, and $E^{+}\left(x_{[-N,N]}\right)=E^{+}\left(y_{[-N,N]}\right)$.

  2. (ii)

$x\sim_{\text{lcu}}y$ if and only if there exists $N\geq 0$ such that both
$x_{[-N,N]}$ and $y_{[-N,N]}$ are synchronizing words, $x_{n}=y_{n}$ for all
$n<-N$, and $E^{-}\left(x_{[-N,N]}\right)=E^{-}\left(y_{[-N,N]}\right)$.

If the latter is true in (i), we can construct an explicit stable local
conjugacy $\gamma:X^{\text{u}}(x,N)\to X^{\text{u}}(y,N)$ by

$\gamma(z)_{n}=\begin{cases}z_{n}&n>N\\\ y_{n}&n\leq N\end{cases}$

for $z\in X^{\text{u}}(x,N)$. Similarly, if the latter is true in (ii), we can
construct an explicity unstable local conjugacy $\gamma:X^{\text{s}}(x,N)\to
X^{\text{s}}(y,N)$ by

$\gamma(z)_{n}=\begin{cases}y_{n}&n\geq-N\\\ z_{n}&n<-N\end{cases}$

for $z\in X^{\text{s}}(x,N)$.

###### Proof.

We will prove (i). It is easy to see that the map $\gamma:X^{\text{u}}(x,N)\to
X^{\text{u}}(y,N)$ is indeed a stable local conjugacy. Conversely, if
$x\sim_{\text{lcs}}y$ via a stable local conjugacy $\gamma$, there is an $N$
such that $X^{\text{u}}(x,N)$ is contained in the domain of $\gamma$,
$x_{[-N,N]}$ and $y_{[-N,N]}$ are both synchronizing words, and
$z_{n}=\gamma(z)_{n}$ for all $n>N$ and $z\in X^{\text{u}}(x,N)$. In
particular $x_{n}=y_{n}$ for all $n>N$. Note that $\gamma$ is a homeomorphism
from $X^{\text{u}}(x,N)$ to $X^{\text{u}}(y,N)$.

We now show that $\gamma$ induces a bijection
$E^{+}\left(x_{[-N,N]}\right)=E^{+}\left(y_{[-N,N]}\right)$. For any $b\in
E^{+}\left(x_{[-N,N]}\right)$, with $|b|=M$, there is a $z\in
X^{\text{u}}(x,N)$ such that $z_{[N+1,N+M+1)}=b$. Observe that
$\gamma(z)_{[N+1,N+M+1)}=b$ implying $b\in E^{+}\left(y_{[-N,N]}\right)$, so
we have shown $E^{+}\left(x_{[-N,N]}\right)\subseteq
E^{+}\left(y_{[-N,N]}\right)$. Since $\gamma$ itself is in particular a
bijection, we similarly have $E^{+}\left(y_{[-N,N]}\right)\subseteq
E^{+}\left(x_{[-N,N]}\right)$, thus proving (i). ∎

######  Example 3.2.

Consider the even shift (see Example 1.4), and consider the two elements
$x=...\mathtt{111.0000}...$ and $y=...\mathtt{111.1000}...$. Note that
$x\sim_{\text{s}}y$ and also that both $x$ and $y$ are synchronizing. However,
since $E^{+}\left(\mathtt{1}^{k}\mathtt{0}^{k+1}\right)\neq
E^{+}\left(\mathtt{1}^{k+1}\mathtt{0}^{k}\right)$ for all $k\geq 1$, we cannot
have $x\sim_{\text{lcs}}y$. Hence $X^{\text{s}}(x)\neq X^{\text{lcs}}(x)$ for
this particular choice of $x$.

######  Example 3.3.

Let $X\subseteq\\{\mathtt{a},\mathtt{b},\mathtt{c}\\}^{\mathbb{Z}}$ be the
shift space defined as the closure of the set of bi-infinite paths on the
graph $G$ below. This is a modified version of the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift to be discussed in Section 7.

$\cdots$$\cdots$$\mathtt{b}$$\mathtt{a}$$\mathtt{b}$$\mathtt{a}$$\mathtt{b}$$\mathtt{a}$$\mathtt{a}$$\mathtt{b}$$\mathtt{b}$$\mathtt{b}$$\mathtt{c}$

The shift space $X$ is a mixing synchronizing system. The proof goes as
follows. This shift space is synchronizing since $\mathtt{ba}$ is a
synchronizing word, see Lemma 7.1. We use the following definition of mixing
for shift spaces: suppose $w,v\in\mathcal{L}(X)$, then there is an $N$ such
that for each $n\geq N$ there is $u$ with $|u|=n$ and $wuv\in\mathcal{L}(X)$.
Let $v_{0}$ denote the bottom-left vertex in the graph of $G$ which has an
edge labeled $\mathtt{c}$ from $v_{0}$ to itself. Consider the words
$w,v\in\mathcal{L}(X)$, and let $p$ and $q$ be finite paths on $G$ such that
their labels are $w$ and $v$ respectively. Let $v_{1}$ denote the target
vertex of $p$ and $v_{2}$ the initial vertex of $q$. Observe that the graph
$G$ is irreducible, so we can find a path $p^{\prime}$ from $v_{1}$ to
$v_{0}$, and a path $q^{\prime}$ from $v_{0}$ to $v_{2}$. Let $w^{\prime}$ be
the label of $p^{\prime}$ and $v^{\prime}$ be the label of $q^{\prime}$. Then
we can see that $ww^{\prime}\mathtt{c}^{k}v^{\prime}v$ is a word in
$\mathcal{L}(X)$ for any $k\geq 0$, hence $X$ is mixing.

Let $p=\overline{\mathtt{ab}}=\ldots\mathtt{ab.aba}\ldots$, which is a
synchronizing periodic point in $X$. Consider the points

$\displaystyle x$ $\displaystyle=\ldots\mathtt{ababaa.aaaaaa}\ldots\text{ ,
and }$ $\displaystyle y$ $\displaystyle=\ldots\mathtt{bbbbbb.bbabab}\ldots$

where $x\in X^{\text{u}}(p)$ and $y\in X^{\text{s}}(p)$. Then in order for $z$
to satisfy $x\sim_{\text{lcs}}z\sim_{\text{lcu}}y$, by Lemma 3.2 we need there
to exist $N\geq 0$ such that

  * •

$x_{[-N,N]}$, $y_{[-N,N]}$, and $z_{[-N,N]}$ are synchronizing,

  * •

$z_{n}=x_{n}$ for all $n>N$,

  * •

$z_{n}=y_{n}$ for all $n<N$,

  * •

$E^{+}\left(z_{[-N,N]}\right)=E^{+}\left(x_{[-N,N]}\right)$, and

  * •

$E^{-}\left(z_{[-N,N]}\right)=E^{-}\left(y_{[-N,N]}\right)$.

For $N\geq 2$, $x_{[-N,N]}=\ldots\mathtt{ba}^{N+3}$ and
$y_{[-N,N]}=\mathtt{b}^{N+2}\mathtt{a}\ldots$ are synchronizing. Observe that
for any such $N$, we need $z_{[-N,N]}$ to be such that
$E^{+}\left(z_{[-N,N]}\right)=E^{+}\left(x_{[-N,N]}\right)$ and
$E^{-}\left(z_{[-N,N]}\right)=E^{-}\left(y_{[-N,N]}\right)$. Furthermore, we
can see from the graph $G$ that $E^{+}(w)=E^{+}\left(x_{[-N,N]}\right)$ if and
only if $w=w^{\prime}\mathtt{ba}^{N+2}$ for some other word $w^{\prime}$.
Likewise, $E^{-}(w)=E^{-}\left(y_{[-N,N]}\right)$ if and only if
$w=\mathtt{b}^{N+1}\mathtt{a}w^{\prime}$ for some other word $w^{\prime}$.
Hence $z_{[-N,N]}$ must have the form

$z_{[-N,N]}=\mathtt{b}^{N+2}w\mathtt{a}^{N+3}\,.$

However, this is a contradiction since $|z_{[-N,N]}|=2N+1$ but the above
conditions say that we need at least $|z_{[-N,N]}|\geq 2N+5$. Hence no such
$z$ satisfying $x\sim_{\text{lcs}}z\sim_{\text{lcu}}y$ can exist.

##  4\. The Homoclinic and Heteroclinic Algebras of Shift Spaces

In [6] we defined several $C^{\ast}$ algebras associated to synchronizing
systems, based on work by Thomsen [21]. These are built from the equivalence
relations discussed in Section 3, which may be topologized so as to produce
étale groupoids.

In the case of a shift space $X$, the homoclinic and heteroclinic algebras of
$(X,\sigma)$ are AF-algebras and can be computed from certain Bratteli
diagrams. First we will discuss how one can construct an étale groupoid from a
Bratteli diagram. Then we will show how to construct Bratteli diagrams which
produce the homoclinic and heteroclinic algebras of a shift space. Thomsen
constructs the homoclinic algebra of a shift space in [21], and it is implicit
that a similar construction is possible for the heteroclinic algebras of a
shift space.

Bratteli diagrams were introduced by Brattli in [3]. A Bratteli diagram
$B=(V,E)$ is an indexed collection of vertices $V=\\{V_{n}\\}_{n\geq N}$ and
an indexed collection of edges $E=\\{E_{n}\\}_{n\geq N}$. For our purposes we
will index the vertex and edge sets starting at some $N\in\mathbb{Z}$. In a
Bratteli diagram one thinks of the edges in $E_{n}\in E$ as going from
vertices in $V_{n}$ to vertices in $V_{n+1}$. For an edge $e\in E_{n}$, let
$i(e)\in V_{n}$ denote the initial vertex of $e$ and $t(e)\in V_{n+1}$ denote
the terminal vertex of $e$.

We will now construct a groupoid $G(B)$ from a Bratteli diagram $B$. Let

$B^{\infty}=\\{(e_{N},e_{N+1},\ldots)\mid t(e_{n})=i(e_{n+1})\text{ for all
}n\geq N\\}$

be the set of infinite paths in the Bratteli diagram $B$, topologized as
subspace of $\displaystyle\prod_{n\geq N}E_{n}$. Let $B(e,M)\subseteq
B^{\infty}$ be defined as

$B(e,M)=\\{f\in B^{\infty}\mid f_{n}=e_{n}\text{ for all }N\leq n\leq M\\}\,.$

The sets $B(e,M)$ are a clopen basis for the topology on $B^{\infty}$. Define
$G(B)$ to be the set

$G(B)=\\{(e,e^{\prime})\in B^{\infty}\times B^{\infty}\mid\exists M\geq
N\text{ such that }e_{n}=e^{\prime}_{n}\text{ for all }n>M\\}\,.$

If $(e,e^{\prime})\in G(B)$ and $e_{n}=e^{\prime}_{n}$ for all $n>M$ for some
$M$, then in particular $t(e_{M})$ and $t(e^{\prime}_{M})$ are the same
vertex. Hence for each $(e,e^{\prime})\in G(B)$ we have, for some $M$, a
bijection $\gamma:B(e,M)\to B(e^{\prime},M)$ defined by

$\gamma(f)=(e^{\prime}_{0},e^{\prime}_{1},\ldots,e^{\prime}_{M},f_{M+1},\ldots)\,.$

The sets $\Gamma(e,e^{\prime},M)=\\{(f,\gamma(f))\mid f\in B(e,M)\\}$ are a
basis for a topology on $G(B)$. In fact, with this topology $G(B)$ is an étale
groupoid — see [13, Theorem 3.5.6]. For $(e,e^{\prime})\in G(B)$ we define
$s(e,e^{\prime})=e$ and $r(e,e^{\prime})=e^{\prime}$, and remark that the unit
space $G(B)^{0}$ is identified with $B^{\infty}$.

Given a Bratteli diagram $B=(V,E)$, one can produce an AF-algebra
$C^{\ast}(B)$. Conveniently, we may compute the $K$-theory of this AF-algebra
from the Bratteli diagram itself, that is,

$K_{0}\big{(}C^{\ast}(B)\big{)}\cong\varinjlim\left(\mathbb{Z}V_{n},A_{n}\right)$

where $A_{n}:Z_{n}\to Z_{n+1}$ is the $|V_{n+1}|$ by $|V_{n}|$ matrix with
non-negative integer entries encoding the edges between $V_{n}$ and $V_{n+1}$.
That is

$A_{n}(v)=\sum_{e\in i^{-1}(v)}t(e)$

for all $v\in V_{n}$. We call $A_{n}$ the _transition matrices_.

###  4.1. Homoclinic Algebra

We denote by $\mathcal{L}_{n}(X)$ the words of length $n$ in a shift space
$X$, in other words $\mathcal{L}_{n}(X)=\\{w\in\mathcal{L}(X)\mid|w|=n\\}$.
Recall that the context of $w\in\mathcal{L}(X)$, denoted $E(w)$, is given in
Definition 2.2 as the set

$E(w)=\\{(a,b)\in\mathcal{L}(X)\times\mathcal{L}(X)\mid
awb\in\mathcal{L}(X)\\}\,.$

######  Definition 4.1.

Let $X$ be a shift space. Then for each $n\geq 0$ we define an equivalence
relation on $\mathcal{L}_{n}(X)$ by $w\sim v$ if and only if $E(w)=E(v)$. Then
we say $w$ and $v$ are _context equivalent_.

We will now construct a Bratteli diagram $B^{\text{lc}}(X)$, where $X$ is a
shift space over the alphabet $\mathcal{A}$. Let $V_{-1}=\\{*\\}$ be a
singleton set, and let $V_{n}=\mathcal{L}_{2n+1}(X)/\sim$ where $\sim$ denotes
the context equivalence relation as in Definition 4.1. We define the edge set
for $n=-1$ to be $E_{-1}=\\{(*,[a])\mid a\in\mathcal{A}\\}$. Then for $n\geq
0$ we define the edge sets

$E_{n}=\left\\{\big{(}[w],[awb]\big{)}\,\middle|\,[w]\in
V_{n},\,a,b\in\mathcal{A}\text{ such that }(a,b)\in E(w)\right\\}\,.$

If $[v]=[w]$ for $w,v\in\mathcal{L}_{2n+1}(X)$, then $E(w)=E(v)$ by
definition. If $a,b\in\mathcal{A}$ such that $(a,b)\in E(w)$, then
$awb,avb\in\mathcal{L}_{2n+3}(X)$ and furthermore $E(awb)=E(avb)$. Hence the
operation $[w]\mapsto[awb]$ is a well-defined operation on context equivalence
classes whenever $(a,b)\in E(w)$. In short, for each $a,b\in\mathcal{A}$ such
that $(a,b)\in E(w)$, we get an edge from $[w]\in V_{n}$ to $[awb]\in V_{n+1}$
which we label as $(a,b)$.

######  Theorem 4.1.

Suppose $X$ be a shift space. Then $G\left(B^{\text{lc}}(X)\right)\cong
G^{\text{lc}}(X,\sigma)$.

###### Proof.

Let $x\in X$. Then it is straightforward to see from the construction of
$B^{\text{lc}}(X)$ that $x$ corresponds uniquely to the path
$\rho(x)=\\{e_{n}\\}_{n\geq-1}$ where $t(e_{-1})=[x_{0}]$ and
$t(e_{n})=[x_{[-n,n]}]$ for all $n\geq 0$. In particular each $e_{n}$ is the
edge $\big{(}[x_{[-n,n]}],[x_{[-n-1,n+1]}]\big{)}\in E_{n}$. Furthermore, any
element
$(x_{0},(x_{-1},x_{1}),(x_{-2},x_{2}),\ldots)\in\left(B^{\text{lc}}(X)\right)^{\infty}$
corresponds to the sequence $\ldots x_{-2}x_{-1}x_{0}x_{1}x_{2}\ldots\in X$.
We denote this bijection $\rho:X\to\left(B^{\text{lc}}(X)\right)^{\infty}$.

From Lemma 3.1, we know that $x,y\in X$ satisfy $x\sim_{\text{lc}}y$ if and
only if there exists $M\geq 0$ such that $x_{n}=y_{n}$ for all $|n|>M$ and
$E\left(x_{[-M,M]}\right)=E\left(y_{[-M,M]}\right)$. This implies that
$(\rho(x),\rho(y))\in G\left(B^{\text{lc}}(X)\right)$. Conversely, if
$(e,e^{\prime})\in G\left(B^{\text{lc}}(X)\right)$, then there is an $M$ such
that $e_{n}=e^{\prime}_{n}$ for all $n>M$. Since $\rho$ is a bijection,
$e=\rho(x)$ and $e^{\prime}=\rho(y)$ for some $x,y\in X$. Then since
$t(e_{M})=[x_{[-M,M]}]=[y_{[-M,M]}]=t(e^{\prime}_{M})$, we have
$E\left(x_{[-M,M]}\right)=E\left(y_{[-M,M]}\right)$. Lastly since
$e_{n}=e^{\prime}_{n}$ for all $n>M$, it follows that $x_{n}=y_{n}$ for all
$n>M$, implying $x\sim_{\text{lc}}y$. Hence we have a bijection
$\Phi:G^{\text{lc}}(X,\sigma)\to G\left(B^{\text{lc}}(X)\right)$ defined by
$\Phi(x,y)=(\rho(x),\rho(y))$ which clearly preserves the groupoid structure.

Let $\gamma:C\left(x_{[-M,M]}\right)\to C\left(y_{[-M,M]}\right)$ denote a
local conjugacy from $x$ to $y$ in $X$, then the set
$\left\\{(z,\gamma(z))\,\middle|\,z\in C\left(x_{[-M,M]}\right)\right\\}$ is
an open neighborhood of $(x,y)$ in $G^{\text{lc}}(X,\sigma)$. In fact, sets of
this form are a basis for the topology on $G^{\text{lc}}(X,\sigma)$ in the
case when $X$ is a shift space. Finally, to see that $\Phi$ is homeomorphism,
see that

$\Phi\left(\left\\{(z,\gamma(z))\,\middle|\,z\in
C\left(x_{[-M,M]}\right)\right\\}\right)=\Gamma(\rho(x),\rho(y),M)\,.$

Hence $G\left(B^{\text{lc}}(X)\right)\cong G^{\text{lc}}(X,\sigma)$. ∎

From Definition 2.1 we can see that if $w\in\mathcal{L}_{2n+1}(X)$ is
synchronizing then the entire equivalence class $[w]\in V_{n}$ is
synchronizing. Hence we will call $[w]\in V_{n}$ a _synchronizing vertex_.
Suppose $X$ is a synchronizing shift space and $x\in X_{\text{sync}}$ is a
synchronizing point. Then for some $n$ the word $x_{[-n,n]}$ is synchronizing,
so $[x_{[-n,n]}]\in V_{n}$ is a synchronizing vertex. Furthermore if $w$ is
synchronizing and $(a,b)\in E(w)$, then $awb$ is also synchronizing. Thus if a
path $e\in\left(B^{\text{lc}}(X)\right)^{\infty}$ passes through a
synchronizing vertex, then every subsequent vertex in $e$ must also be
synchronizing. Let $\rho:X\to\left(B^{\text{lc}}(X)\right)^{\infty}$ be the
bijection defined in the proof of Theorem 4.1. Then the image of
$X_{\text{sync}}$ under $\rho$ is the subset of all paths in
$\left(B^{\text{lc}}(X)\right)^{\infty}$ which eventually pass through a
synchronizing vertex. Hence, following Theorem 4.1,
$G^{\text{lc}}_{\text{sync}}(X,\sigma)$ (defined in Theorem [6, Theorem 5.8])
is isomorphic to the subgroupoid of all $(e,e^{\prime})\in
G\left(B^{\text{lc}}(X)\right)$ such that
$e,e^{\prime}\in\rho\left(X_{\text{sync}}\right)$.

###  4.2. Heteroclinic Algebras

We will now construct a series of Bratteli diagrams which together will give
us the groupoid $G^{\text{lcs}}(X,\sigma,p)$ for a synchronizing shift space.
Let $(X,\sigma)$ be a synchronizing shift space over the alphabet
$\mathcal{A}$, and let $p\in X$ be a synchronizing periodic point. Since $p$
is periodic and synchronizing, then for each $N$ there exists $k=k(N)\geq N$
such that $p_{[-k,-N]}$ is a synchronizing word. Hence the follower set of
$p_{(-\infty,-N]}$ agrees with $p_{[-k,-N]}$, see Section 3.1. We will denote
$E^{+}\left(p_{[-k,-N]}w\right)$ as $E^{+}\left(p_{(-\infty,-N]}w\right)$ for
any $w\in E^{+}\left(p_{[-k,-N]}\right)$.

We now fix $N\geq 0$ and construct a Bratteli diagram
$B^{\text{lcs}}_{N}(X,p)$ which will produce all stable local conjugacy
equivalence classes of elements in $X^{\text{u}}(p,N)$. Recall
$X^{\text{u}}(p,N)$ is defined in Section 3.1 as the set

$X^{\text{u}}(p,N)=\\{x\in X\mid x_{n}=p_{n}\text{ for all }n\leq-N\\}\,.$

For simplifying notation moving forward, denote
$E^{+}_{n}\left(u\right)=\mathcal{L}_{n}(X)\cap E^{+}\left(u\right)$ for
$u\in\mathcal{L}(X)$. Let $V_{-N}=\\{*\\}$ be a singleton set. Then for $n>-N$
let the set of vertices $V_{n}$ in the Bratteli diagram be

$V_{n}=E^{+}_{n-N}\left(p_{(-\infty,-N]}\right)\big{/}\sim$

where $w\sim v$ if and only if
$E^{+}\left(p_{(-\infty,-N]}w\right)=E^{+}\left(p_{(-\infty,-N]}v\right)$. We
then define the set of edges $E_{n}$ from $V_{n}$ to $V_{n+1}$ as

$E_{n}=\left\\{([w],[wa])\,\middle|\,[w]\in V_{n},a\in
E^{+}_{1}\left(p_{(-\infty,-N]}w\right)\right\\}\,.$

Similar to the homoclinic case, the operation $[w]\mapsto[wa]$ is a well-
defined operation on equivalence classes. In summary, for each
$a\in\mathcal{A}$ such that $a\in E^{+}(w)$, we get an edge from $[w]\in
V_{n}$ to $[wa]\in V_{n+1}$ which we think of as being labeled ‘a’.

Next note that for each $N$ we have an inclusion
$\left(B^{\text{lcs}}_{N}(X,p)\right)^{\infty}\subseteq\left(B^{\text{lcs}}_{N+1}(X,p)\right)^{\infty}$
by the map

$(e_{-N+1},e_{-N+2},\ldots)\mapsto(p_{N},e_{-N+1},e_{-N+2},\ldots)$

where $p_{N}$ is the edge from the singleton set $V_{-(N+1)}$ to $[p_{N}]\in
V_{N}$ in the Bratteli diagram $B^{\text{lcs}}_{N+1}(X,p)$. Hence, by our
definition of the groupoid of a Bratteli diagram, we get an induced inclusion
$G\left(B^{\text{lcs}}_{N}(X,p)\right)\subseteq
G\left(B^{\text{lcs}}_{N+1}(X,p)\right)$ for each $N\geq 0$.

We omit the construction of $B^{\text{lcu}}_{N}(X,p)$ since it is very similar
(i.e. it is built on the predecessor set of $p_{[N,\infty)}$ for each $N\geq
0$), but we remark that there are identical inclusions of
$G\left(B^{\text{lcu}}_{N}(X,p)\right)$ into
$G\left(B^{\text{lcu}}_{N+1}(X,p)\right)$.

######  Theorem 4.2.

Suppose $X$ is a synchronizing shift space. Then

  1. (i)

$\displaystyle G^{\text{lcs}}(X,\sigma,p)\cong\bigcup_{N\geq
0}G\left(B^{\text{lcs}}_{N}(X,p)\right)$, and

  2. (ii)

$\displaystyle G^{\text{lcu}}(X,\sigma,p)\cong\bigcup_{N\geq
0}G\left(B^{\text{lcu}}_{N}(X,p)\right)$.

###### Proof.

We will show the proof of (i). First we will show that for each $N\geq 0$ we
have a bijection
$\rho_{N}:X^{\text{u}}(p,N)\to\left(B^{\text{lcs}}_{N}(X,p)\right)^{\infty}$.
For each $x\in X^{\text{u}}(p,N)$, by definition, $x_{n}=p_{n}$ for all $n\leq
N$. Hence it is easy to see from the construction of $B^{\text{lcs}}_{N}(X,p)$
that the map $\rho_{N}$ defined by

$\rho_{N}(x)=x_{(-N,\infty)}=(x_{-N+1},x_{-N+2},\ldots)$

is a bijection.

Recall that $\displaystyle X^{\text{u}}(p)=\bigcup_{N\geq 0}X^{\text{u}}(p,N)$
by the definition of unstable equivalence on shift spaces. We will show that
$\rho_{N}$ is compatible with the inclusions $X^{\text{u}}(p,N)\subseteq
X^{\text{u}}(p,N+1)$ and
$\left(B^{\text{lcs}}_{N}(X,p)\right)^{\infty}\subseteq\left(B^{\text{lcs}}_{N+1}(X,p)\right)^{\infty}$,
and hence the $\rho_{N}$ lift to a bijection
$\displaystyle\rho:X^{\text{u}}(p)\to\bigcup_{N\geq
0}\left(B^{\text{lcs}}_{N}(X,p)\right)^{\infty}$. This compatibility is easy
to see, as $\rho_{N+1}(x)=(p_{-N},x_{-N+1},x_{-N+2},\ldots)$ for $x\in
X^{\text{u}}(p,N)\subseteq X^{\text{u}}(p,N+1)$. Similarly the inclusion of
$\rho_{N}(x)\in\left(B^{\text{lcs}}_{N}(X,p)\right)^{\infty}$ into
$\left(B^{\text{lcs}}_{N+1}(X,p)\right)^{\infty}$ is given by
$\rho_{N}(x)=(x_{-N+1},x_{-N+2},\ldots)\mapsto(p_{-N},x_{-N+1},x_{-N+2},\ldots)$.

If $x,y\in X^{\text{u}}(p)$ and $x\sim_{\text{lcs}}y$, then by Lemma 3.2 there
exists $M\geq 0$ such that $x_{[-M,M]}$ and $y_{[-M,M]}$ are both
synchronizing words, $x_{n}=y_{n}$ for all $n>M$, and
$E^{+}\left(x_{[-M,M]}\right)=E^{+}\left(y_{[-M,M]}\right)$. Furthermore,
since $x,y\in X^{\text{u}}(p)$, there exists $N>M$ such that $x,y\in
X^{\text{u}}(p,N)$. Note that since $x_{[-M,M]}$ and $y_{[-M,M]}$ are both
synchronizing words, we also have
$E^{+}\left(p_{(-\infty,-N]}x_{(-N,M]}\right)=E^{+}\left(p_{(-\infty,-N]}y_{(-N,M]}\right)$.
In total, this means that the paths $\rho_{N}(x)=x_{(-N,\infty)}$ and
$\rho_{N}(y)=y_{(-N,\infty)}$ satisfy $\rho_{N}(x)_{n}=\rho_{N}(y)_{n}$ for
all $n>M$, hence $(\rho_{N}(x),\rho_{N}(y))\in
G\left(B^{\text{lcs}}_{N}(X,p)\right)$.

Conversely, given $(e,e^{\prime})\in G\left(B^{\text{lcs}}_{N}(X,p)\right)$
for some $N\geq 0$, it is clear from the construction of
$B^{\text{lcs}}_{N}(X,p)$ that the points $\rho_{N}^{-1}(e)$ and
$\rho_{N}^{-1}(e^{\prime})$ are stably locally conjugate in $X^{u}(p,N)$. Let
$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,N)}$ denote the set

$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,N)}=\\{(x,y)\in
G^{\text{lcs}}(X,\sigma,p)\mid x,y\in X^{\text{u}}(p,N)\\}\,.$

Then for each $N\geq 0$ we shown there is a bijection

$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,N)}\mapsto
G\left(B^{\text{lcs}}_{N}(X,p)\right)$

via the map $(x,y)\mapsto(\rho_{N}(x),\rho_{N}(y))$. This lifts to a bijection
$\displaystyle\Phi:G^{\text{lcs}}(X,\sigma,p)\to\bigcup_{N\geq
0}G\left(B^{\text{lcs}}_{N}(X,p)\right)$ defined by
$\Phi(x,y)=(\rho(x),\rho(y))$. Similar to the proof of 4.1, the map $\Phi$ is
a homeomorphism, hence $\displaystyle
G^{\text{lcs}}(X,\sigma,p)\cong\bigcup_{N\geq
0}G\left(B^{\text{lcs}}_{N}(X,p)\right)$. ∎

Lastly, we will show that in some cases it is sufficient (up to Morita
equivalence) to compute $B^{\text{lcs}}_{0}(X,p)$. In particular it is the
case with mixing sofic shifts, as shown in the following theorem.

######  Theorem 4.3.

Let $X$ be a mixing sofic shift. Then,

  1. (1)

$G\left(B^{\text{lcs}}_{0}(X,p)\right)$ and $G^{\text{lcs}}(X,\sigma,p)$ are
Morita equivalent, and

  2. (2)

$G\left(B^{\text{lcu}}_{0}(X,p)\right)$ and $G^{\text{lcu}}(X,\sigma,p)$ are
Morita equivalent.

###### Proof.

We will show the proof in the stable case. We use [7, Definition 3.8] and [7,
Theorem 3.12], and show that $G\left(B^{\text{lcs}}_{0}(X,p)\right)$ and
$G^{\text{lcs}}(X,\sigma,p)$ are Kakutani equivalent, and hence Morita
equivalent. Observe from the proof of Theorem 4.2 that the map
$(x,y)\mapsto(\rho_{0}(x),\rho_{0}(y))$ gives an isomorphism
$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,0)}\to
G\left(B^{\text{lcs}}_{0}(X,p)\right)$, where
$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,0)}$ is defined as

$G^{\text{lcs}}(X,\sigma,p)|_{X^{\text{u}}(p,0)}=\\{\gamma\in
G^{\text{lcs}}(X,\sigma,p)\mid r(\gamma),s(\gamma)\in X^{\text{u}}(p,0)\\}\,.$

Furthermore Note that $X^{\text{u}}(p,0)$ and
$\left(B^{\text{lcs}}_{0}(X,p)\right)^{\infty}$ are both clopen in the
topology on the unit spaces of $G^{\text{lcs}}(X,\sigma,p)$ and
$G\left(B^{\text{lcs}}_{0}(X,p)\right)$ respectively. Lastly, we must now show
that that $X^{\text{u}}(p,0)\subset X^{\text{u}}(p)$ is
$G^{\text{lcs}}(X,\sigma,p)$-full (see [11]), that is to say for all $y\in
X^{\text{u}}(p)$ there is some $x\in X^{\text{u}}(p,0)$ such that
$x\sim_{\text{lcs}}y$. This follows from Lemma [6, Lemma 6.7] since sofic
shifts are finitely presented. ∎

######  Definition 4.2.

In summary, given a synchronizing shift $X$ and a fixed synchronizing periodic
point $p\in X$, we define the following $C^{\ast}$-algebras as in [6].

  1. (i)

The _homoclinic algebra_ of $X$ is
$A(X,\sigma)=C^{\ast}(G^{\text{lc}}(X,\sigma))$.

  2. (ii)

The _stable synchronizing algebra_ of $X$ is
$S(X,\sigma,p)=C^{\ast}(G^{\text{lcs}}(X,\sigma,p))$.

  3. (iii)

The _unstable synchronizing algebra_ of $X$ is
$U(X,\sigma,p)=C^{\ast}(G^{\text{lcu}}(X,\sigma,p))$.

  4. (iv)

The _synchronizing ideal_ of $X$ is

$\mathcal{I}_{\text{sync}}(X,\sigma)=C^{\ast}\left(G^{\text{lc}}_{\text{sync}}(X,\sigma)\right)=C^{\ast}\left(G^{\text{lc}}(X,\sigma)|_{X_{\text{sync}}}\right)\subseteq
A(X,\sigma)\,.$

The stable and unstable synchronizing algebras are collectively called the
_heteroclinic synchronizing algebras_ of $X$.

Note that in general the heteroclinic synchronizing algebras are related to
but not the same as, or even Morita equivalent to, the _heteroclinic algebras_
defined by Thomsen in [21]. This is due to the fact that Thomsen builds the
heteroclinic algebras out of the set of all periodic points, while we are
restricting to a single synchronizing periodic point. By [6, Theorem 5.5], the
choice of synchronizing periodic point does not matter (up to Morita
equivalence).

###  4.3. Short Exact Sequence and Morita Equivalence

Suppose that $(X,\sigma)$ is a synchronizing shift space. In [6, Theorem 5.8]
we have shown there is a short exact sequence determined by the synchronizing
ideal. Since the above groupoids are all AF-groupoids, and hence amenable,
this short exact sequence has the form

$0\longrightarrow\mathcal{I}_{\text{sync}}(X,\sigma)\longrightarrow
A(X,\sigma)\longrightarrow C^{\ast}\left(G^{\text{lc}}_{\text{non-
sync}}(X,\sigma)\right)\longrightarrow 0$

where $G^{\text{lc}}_{\text{non-
sync}}(X,\sigma)=G^{\text{lc}}(X,\sigma)|_{X_{\text{non-sync}}}$. In the case
when $X$ is a mixing sofic shift, we also have that
$\mathcal{I}_{\text{sync}}(X,\sigma)$ is Morita equivalent to
$S(X,\sigma,p)\otimes U(X,\sigma,p)$ for any choice of synchronizing periodic
point $p\in X$, see [6, Theorem 6.10].

##  5\. The Even Shift

Recall from Example 1.4 that the even shift is a shift space in the alphabet
$\\{\mathtt{0},\mathtt{1}\\}$ whose elements don’t contain any of the words in
the set $F=\\{\mathtt{10}^{2k+1}\mathtt{1}\mid k\geq 0\\}$. That is to say
that the elements of the even shift are infinite binary sequences which have
an even number of consecutive zeros between any two ones. We will denote the
even shift as $X_{\text{even}}$.

###  5.1. Homoclinic Algebra

We will now construct the Brattli diagram $B^{\text{lc}}(X_{\text{even}})$ as
in Section 4.1. To this end, we must describe the context equivalence classes
of words in $\mathcal{L}(X_{\text{even}})$. If we assume that $n\geq 1$ and
$w\neq\mathtt{0}^{2n+1}$, then
$w=\mathtt{0}^{k}\mathtt{1}\dots\mathtt{1}\mathtt{0}^{l}$ for some $k,l\geq
0$. It is always the case in the even shift that the zero word of any length
can be appended to either side of any word $w$, so we consider pairs
$(a,b)\in\mathcal{L}(X_{\text{even}})\times\mathcal{L}(X_{\text{even}})$ of
the form

$a=...\mathtt{1}\mathtt{0}^{r}\qquad b=\mathtt{0}^{s}\mathtt{1}...$

In this case, $awb$ will be a word in the even shift if and only if $r+k$ and
$l+s$ are both even. Hence if $w$ and $v$ are both non-zero words of length
$2n+1$ we have $E(w)=E(v)$ if and only if the parity of zeros on each side of
$w$ and $v$ both match. In particular, a word
$w\in\mathcal{L}(X_{\text{even}})$ is synchronizing if and only if $w$
contains a $\mathtt{1}$. In the case of the word
$\mathtt{0}^{2n+1}\in\mathcal{L}_{2n+1}(X_{\text{even}})$, we can see that
both $(\mathtt{1},\mathtt{0})$ and $(\mathtt{0},\mathtt{1})$ are in
$E(\mathtt{0}^{2n+1})$ but $(\mathtt{1},\mathtt{1})$ is not, which cannot be
the case for any $w\neq\mathtt{0}^{2n+1}$. This means $E(w)\neq
E(\mathtt{0}^{2n+1})$ whenever $w\neq\mathtt{0}^{2n+1}$. Lastly, when $n=0$,
$\mathcal{L}_{1}(X_{\text{even}})=\\{\mathtt{0},\mathtt{1}\\}$ and
$E(\mathtt{0})\neq E(\mathtt{1})$ so the words $\mathtt{0}$ and $\mathtt{1}$
each form their own equivalence class.

In summary, for $n=0$ we have two context equivalence classes, and hence
$V_{0}$ has two vertices in the Brattli diagram
$B^{\text{lc}}(X_{\text{even}})$. For $n\geq 1$, there are five context
equivalence classes and so five vertices in $V_{n}$. We then get edges from
$V_{n}$ to $V_{n+1}$ as described in Section 4.1. For example there is an edge
from $[\mathtt{1}]\in V_{0}$ to
$[\mathtt{111}]=\\{\mathtt{111},\mathtt{100},\mathtt{001}\\}\in V_{1}$ coming
from the pair $(\mathtt{1},\mathtt{1})\in E(\mathtt{1})$. For another example,
there are two edges from $[\mathtt{0}]\in V_{0}$ to $[\mathtt{111}]\in V_{1}$
coming from the pairs $(\mathtt{1},\mathtt{0}),(\mathtt{0},\mathtt{1})\in
E(\mathtt{0})$. This situation is depicted in Figure 1. The AF-algebra
corresponding to $B^{\text{lc}}(X_{\text{even}})$ is isomorphic to
$A(X_{\text{even}},\sigma)$ by Theorem 4.1. We note that there is a slight
discrepancy between the Bratteli diagram in Figure 1 and the Bratteli diagram
in [21, Example 3.5], in particular the edges appear to be incorrect in
Thomsen’s diagram.

$\mathtt{1}$$\mathtt{0}$$\mathtt{111},\mathtt{100},\mathtt{001}$$\mathtt{110}$$\mathtt{011}$$\mathtt{010}$$\mathtt{000}$$\mathtt{11111},\mathtt{11001},$$\mathtt{10011},\mathtt{11100},$$\mathtt{00111},\mathtt{00100},$$\mathtt{10000},\mathtt{00001}$$\mathtt{11110},\mathtt{11000},$$\mathtt{10010},\mathtt{00110}$$\mathtt{01111},\mathtt{01001},$$\mathtt{00011},\mathtt{01100}$$\mathtt{01110},\mathtt{01000},$$\mathtt{00010}$$\mathtt{00000}$$\mathtt{1111111},\dots$$\mathtt{1111110},\dots$$\mathtt{0111111},\dots$$\mathtt{0111110},\dots$$\mathtt{0000000}$$\vdots$$\vdots$$\vdots$$\vdots$$\vdots$
Figure 1. The Bratteli diagram $B^{\text{lc}}(X_{\text{even}})$ for the even
shift. Paths in this Bratteli diagram indicate how to inductively build local
conjugacy equivalence classes in the even shift.

As described in Section 4, we can compute the $K$-theory of
$A(X_{\text{even}},\sigma)$ directly from the Brattli diagram itself,

$K_{0}\big{(}A(X_{\text{even}},\sigma)\big{)}\cong\varinjlim\left(\mathbb{Z}V_{n},A_{n}\right)$

where $A_{n}$ are the transition matrices encoding the edge relation in
$B^{\text{lc}}(X_{\text{even}})$. In this case, $|V_{n}|=5$ and $A_{n}$ is the
matrix

$A=\begin{bmatrix}1&1&1&1&2\\\ 1&0&1&0&0\\\ 1&1&0&0&0\\\ 1&0&0&0&0\\\
0&0&0&0&1\end{bmatrix}$

for all $n\geq 1$. Hence

$K_{0}\big{(}A(X_{\text{even}},\sigma)\big{)}\cong\varinjlim\left(\mathbb{Z}^{5},A\right)$

Note that the direct limit can be computed as
$\varinjlim\left(\mathbb{Z}^{5},A\right)\cong\big{(}\mathbb{Z}^{5}\times\mathbb{N}\big{)}/\sim$
where, for $n\leq k$, $(v,n)\sim(w,k)$ if and only if $vA^{k-n+l}=wA^{l}$ for
some $l\geq 0$.

###  5.2. Heteroclinic Synchronizing Algebras and Synchronizing Ideal

Notice that in the computation of
$K_{0}\big{(}A(X_{\text{even}},\sigma)\big{)}$, if we restrict to the
synchronizing vertices we get the transition matrix

$A_{\text{sync}}=\begin{bmatrix}1&1&1&1\\\ 1&0&1&0\\\ 1&1&0&0\\\
1&0&0&0\end{bmatrix}\,.$

Consequently, we obtain

$K_{0}\big{(}\mathcal{I}_{\text{sync}}(X_{\text{even}},\sigma)\big{)}\cong\varinjlim\left(\mathbb{Z}^{4},A_{\text{sync}}\right)\,.$

Next we will compute the Bratteli diagrams
$B^{\text{lcs}}_{0}(X_{\text{even}},p)$ and
$B^{\text{lcu}}_{0}(X_{\text{even}},p)$ where $p=\overline{\mathtt{1}}$ is the
sequence $\overline{\mathtt{1}}=\ldots\mathtt{11.111}\ldots$, which is a
synchronizing fixed point in the even shift. Observe that the follower set of
$p_{(-\infty,0]}=\ldots\mathtt{111}$ is the same as $E^{+}(\mathtt{1})$. Hence
in $B^{\text{lcs}}_{0}(X_{\text{even}},p)$, we only have two equivalence
classes of words in $V_{n}$ for each $n\geq 0$ since $E^{+}(\mathtt{1}w)$ is
determined by the parity of zeros on the right side of $\mathtt{1}w$. This
Bratteli diagram, and additionally $B^{\text{lcu}}_{0}(X_{\text{even}},p)$,
are depicted in Figure 2.

$B^{\text{lcs}}_{0}\left(X_{\text{even}},\overline{\mathtt{1}}\right)$$\ldots\mathtt{111}$$\mathtt{1}$$\mathtt{0}$$\mathtt{11},\mathtt{00}$$\mathtt{10}$$\mathtt{111},\mathtt{001},\mathtt{100}$$\mathtt{110},\mathtt{000}$$\mathtt{1111},\mathtt{0011},$$\mathtt{1001},\mathtt{1100},$$\mathtt{0000}$$\mathtt{1110},\mathtt{0010},$$\mathtt{1000}$$\vdots$$\vdots$$B^{\text{lcu}}_{0}\left(X_{\text{even}},\overline{\mathtt{1}}\right)$$\mathtt{111}\ldots$$\mathtt{1}$$\mathtt{0}$$\mathtt{11},\mathtt{00}$$\mathtt{01}$$\mathtt{111},\mathtt{001},\mathtt{100}$$\mathtt{011},\mathtt{000}$$\mathtt{1111},\mathtt{0011},$$\mathtt{1001},\mathtt{1100},$$\mathtt{0000}$$\mathtt{0111},\mathtt{0001},$$\mathtt{1000}$$\vdots$$\vdots$
Figure 2. The Bratteli diagrams
$B^{\text{lcs}}_{0}(X_{\text{even}},\overline{\mathtt{1}})$ and
$B^{\text{lcu}}_{0}(X_{\text{even}},\overline{\mathtt{1}})$ for the even
shift. Here we are using the synchronizing periodic point
$p=\overline{\mathtt{1}}=\ldots\mathtt{11.111}\ldots$. The top vertex in each
diagram indicates the left-infinite ray
$\overline{\mathtt{1}}_{(-\infty,0]}=\ldots\mathtt{111}$ and the right-
infinite ray $\overline{\mathtt{1}}_{[0,\infty)}=\mathtt{111}\ldots$,
respectively. Then, paths in each diagram indicate how to build stable
(unstable) local conjugacy equivalence classes inductively.

Since $X_{\text{even}}$ is a mixing sofic shift, by Theorem 4.3 we can compute
the $K$-theory of $S(X_{\text{even}},\sigma,p)$ and
$U(X_{\text{even}},\sigma,p)$ from the Bratteli diagrams
$B^{\text{lcs}}_{0}(X_{\text{even}},p)$ and
$B^{\text{lcu}}_{0}(X_{\text{even}},p)$ respectively. From each of the
Bratteli diagrams $B^{\text{lcs}}_{0}(X_{\text{even}},p)$ and
$B^{\text{lcu}}_{0}(X_{\text{even}},p)$, we can see that the transition
matrices are given by

$A_{\text{lcs}}=A_{\text{lcu}}=\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}\,.$

Hence the $K$-theory of $S(X_{\text{even}},\sigma,p)$ and
$U(X_{\text{even}},\sigma,p)$ can be computed as

$\displaystyle K_{0}\big{(}S(X_{\text{even}},\sigma,p)\big{)}$
$\displaystyle\cong\varinjlim\left(\mathbb{Z}^{2},A_{\text{lcs}}\right)\text{
, and }$ $\displaystyle K_{0}\big{(}U(X_{\text{even}},\sigma,p)\big{)}$
$\displaystyle\cong\varinjlim\left(\mathbb{Z}^{2},A_{\text{lcu}}\right)\,.$

We also remark that by the Morita equivalence in [6, Theorem 5.5], the $K_{0}$
groups computed above are independent of our choice of $p$.

Lastly we point out that

$A_{\text{lcs}}\otimes A_{\text{lcu}}=\begin{bmatrix}1&1&1&1\\\ 1&0&1&0\\\
1&1&0&0\\\ 1&0&0&0\end{bmatrix}=A_{\text{sync}}\,.$

This is a direct reflection of the fact from [6, Theorem 6.11] that
$S(X_{\text{even}},\sigma,p)\otimes U(X_{\text{even}},\sigma,p)$ is Morita
equivalent to $\mathcal{I}_{\text{sync}}(X_{\text{even}},\sigma)$, which
follows from that fact that the even shift is mixing and the fact that sofic
shifts are finitely presented.

In particular, observe that since $A$ and $A_{\text{sync}}$ are both
invertible we have

$\text{rank}(K_{0}(A(X_{\text{even}},\sigma)))=5$

while

$\text{rank}(K_{0}(\mathcal{I}_{\text{sync}}(X_{\text{even}},\sigma)))=4\,.$

Since $S(X_{\text{even}},\sigma,p)\otimes U(X_{\text{even}},\sigma,p)$ is
Morita equivalent to $\mathcal{I}_{\text{sync}}(X_{\text{even}},\sigma)$ and
$K$-theory is invariant under Morita equivalence, we conclude that
$A(X_{\text{even}},\sigma)$ cannot be Morita equivalent to
$S(X_{\text{even}},\sigma,p)\otimes U(X_{\text{even}},\sigma,p)$. Since this
fact is true for Smale spaces (see [15]), and consequently shifts of finite
type, we can see that the failure of $X_{\text{even}}$ to be a shift of finite
type can be shown from the $K$-theory of its homoclinic and heteroclinic
algebras.

Note that, as we remarked before, the heteroclinic synchronizing algebras are
distinct from the heteroclinic algebras defined by Thomsen. This can be seen
in the fact that our heteroclinic synchronizing algebras of the even shift do
not pick up on the point of all zeros, unlike the heteroclinic algebras
compute in [21, Example 3.5].

##  6\. The Charge Constrained Shift

Fix a positive integer $c$. Then the _charge constrained shift_
$X_{c}\subseteq\\{\mathtt{+1},-1\\}^{\mathbb{Z}}$ is the set of all sequences
$x\in\\{\mathtt{+1},\mathtt{-1}\\}^{\mathbb{Z}}$ such that the sum $s$ of the
entries of any finite subword of $x$ satisfies $-c\leq s\leq c$. This is a
sofic shift for all $c$, see [4, Example 1.2.7]. The charge constrained shift
admits the following labeled graph presentation with $c+1$ vertices, which we
denote $G_{c}$. Note that $G_{c}$ is an irreducible graph, so $X_{c}$ is
irreducible [4].

$v_{0}$$v_{1}$$v_{2}$$v_{c-1}$$v_{c}$$\mathtt{+1}$$\mathtt{-1}$$\mathtt{+1}$$\mathtt{-1}$$\mathtt{+1}$$\mathtt{-1}$$\cdots$

Note that there are two different ways to embed the graph $G_{c-1}$ into the
graph $G_{c}$. Let $\\{w_{0},w_{1},\dots,w_{c-1}\\}$ denote the vertices of
the graph $G_{c-1}$, then we can embed $G_{c-1}$ into $G_{c}$ via

$\displaystyle w_{i}$ $\displaystyle\mapsto v_{i}\text{ , or }$ $\displaystyle
w_{i}$ $\displaystyle\mapsto v_{i+1}$

for $0\leq i<c$. Hence we get an embedding of $X_{c-1}$ into $X_{c}$. From
another perspective, we get this embedding because for every $x\in X_{c-1}$
the sum $s$ of the entries of any finite subword of $x$ satisfies $-c<-c+1\leq
s\leq c-1<c$.

The primary intention of introducing this particular shift space is that it is
a synchronizing shift for which the set of non-synchronizing points,
$X_{c}\setminus(X_{c})_{\text{sync}}$, is uncountable. The charge constrained
shift is synchronizing because it is formed from a finite labeled graph, hence
it is sofic. Furthermore, $X_{c}$ is a shift space which is _almost of finite
type (AFT)_ , see [2]. The graph $G_{c}$ is indeed the minimal presentation of
$X_{c}$ which is both left-resolving and right-resolving. The even shift from
Example 1.4 is also a shift space which is almost of finite type.

######  Theorem 6.1.

For $c>2$, the set of non-synchronizing points in the shift space $X_{c}$ is
uncountable.

###### Proof.

Fix $c>2$. If $x\in X_{c-1}\subseteq X_{c}$ then there will always be two
distinct bi-infinite paths in $G_{c}$ corresponding to $x$ under the factor
map $\pi:X_{G_{c}}\to X_{c}$. This is because one can see there are two ways
to embed the graph $G_{c-1}$ into $G_{c}$. Assume for the sake of
contradiction that $x\in X_{c-1}\subseteq X_{c}$ and there is an $n$ such that
$x_{[-n,n]}$ is a synchronizing word. Let $p_{1}$ and $p_{2}$ be two distinct
paths on $G_{c}$ which represent the word $x_{[-n,n]}$. By the two embeddings
of $G_{c-1}$ described above, without loss of generality we have

$\displaystyle s(p_{1})=v_{i}$ $\displaystyle s(p_{2})=v_{i+1}$ $\displaystyle
r(p_{1})=v_{j}$ $\displaystyle r(p_{2})=v_{j+1}$

for some $0\leq i,j<c$. In particular, the sum of the entries in $x_{[-n,n]}$
is $j-i$. Observe that then we have both

$\displaystyle\Big{(}(\mathtt{-1})(\mathtt{+1})^{i},(\mathtt{+1})^{c-j}(\mathtt{-1})\Big{)}$
$\displaystyle\in E\left(x_{[-n,n]}\right)\text{ , and }$
$\displaystyle\Big{(}(\mathtt{-1})(\mathtt{+1})^{i+1},(\mathtt{+1})^{c-j-1}(\mathtt{-1})\Big{)}$
$\displaystyle\in E\left(x_{[-n,n]}\right)$

from the existence of $p_{1}$ and $p_{2}$ respectively. Since we are assuming
$x_{[-n,n]}$ is synchronizing,
$\displaystyle\Big{(}(\mathtt{-1})(\mathtt{+1})^{i+1},(\mathtt{+1})^{c-j}(\mathtt{-1})\Big{)}\in
E\left(x_{[-n,n]}\right)$. Thus we can form the word

$w=(\mathtt{+1})^{i+1}x_{[-n,n]}(\mathtt{+1})^{c-j}\,.$

However, the sum of the entries in $w$ is $(i+1)+(j-i)+(c-j)=c+1$. This is a
contradiction since the sum of the entries in $w$ exceeds $c$, hence $w$ is
not a valid word in $X_{c}$. Hence if $x\in X_{c-1}\subseteq X_{c}$ then $x$
cannot be synchronizing.

Observe that $X_{c}$ is uncountable for $c\geq 2$. A quick proof of this
follows from the fact that $X_{2}\subseteq X_{c}$ for $c\geq 2$, and from the
fact that there is an injective function from the uncountable set
$\\{\mathtt{a},\mathtt{b}\\}^{\mathbb{Z}}$ to $X_{2}$ given by
$\mathtt{a}\mapsto(\mathtt{+1})(\mathtt{-1})$ and
$\mathtt{b}\mapsto(\mathtt{-1})(\mathtt{+1})$. Since we are assuming $c>2$ we
thus have that $X_{c-1}$ is uncountable. In conclusion, we have argued that
$X_{c-1}\subseteq X_{c}\setminus(X_{c})_{\text{sync}}$, and it follows that
the set $X_{c}\setminus(X_{c})_{\text{sync}}$ is uncountable. ∎

##  7\. The $\mathtt{a}^{n}\mathtt{b}^{n}$-Shift

What we call the $\mathtt{a}^{n}\mathtt{b}^{n}$-shift is a modified version of
what is called the context-free shift in [4]. We let the
_$\mathtt{a}^{n}\mathtt{b}^{n}$ -shift_ be the closure of the set of sequences
in $\\{\mathtt{a},\mathtt{b}\\}^{\mathbb{Z}}$ where any finite string of
$\mathtt{a}$’s, if it is followed by a string of $\mathtt{b}$’s, is followed
by a finite string of $\mathtt{b}$’s of the same length. We denote this shift
space $X_{\mathtt{ab}}\subseteq\\{\mathtt{a},\mathtt{b}\\}^{\mathbb{Z}}$.
Alternatively one can think of this as the closure of the set of bi-infinite
sequences formed from freely concatenating strings in the set
$\\{\mathtt{a}^{n}\mathtt{b}^{n}\mid n\geq 1\\}$. From this latter fact, the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift is by definition a _coded system_ [8].
However, it is in particular a synchronizing shift.

######  Lemma 7.1.

The $\mathtt{a}^{n}\mathtt{b}^{n}$-shift is a synchronizing shift.

###### Proof.

We will show that the word $\mathtt{ba}\in\mathcal{L}(X_{\mathtt{ab}})$ is a
synchronizing word. Any word that can be added on the left of $\mathtt{ba}$ is
essentially of the form $w\mathtt{b}\mathtt{a}^{n}\mathtt{b}^{n-1}$, and word
that can be added on the right is of the form
$\mathtt{a}^{m-1}\mathtt{b}^{m}\mathtt{a}v$ — where $v$ and $w$ are arbitrary.
Observe that
$w\mathtt{b}\mathtt{a}^{n}\mathtt{b}^{n}\mathtt{a}^{m}\mathtt{b}^{m}\mathtt{a}v$
is a valid word in the $\mathtt{a}^{n}\mathtt{b}^{n}$-shift, hence
$\mathtt{ba}$ is a synchronizing word. The irreducibility of the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift can be seen from considering the case
when $w=w^{\prime}\mathtt{b}\mathtt{a}^{n+k}\mathtt{b}^{n}$ and
$v=\mathtt{a}^{m}\mathtt{b}^{m+l}\mathtt{a}v^{\prime}$, then
$w\mathtt{b}^{k}\mathtt{a}^{l}v$ is a valid word in $X_{\mathtt{ab}}$. ∎

######  Lemma 7.2.

Suppose $w\in\mathcal{L}(X_{\mathtt{ab}})$ is a word in the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift, then $w$ is synchronizing if and only if
$\mathtt{ba}\sqsubseteq w$.

###### Proof.

Since $\mathtt{ba}$ is synchronizing, as shown in the proof of Lemma 7.1,
$\mathtt{ba}\sqsubseteq w$ implies $w$ is synchronizing. Conversely, assume
$\mathtt{ba}\not\sqsubseteq w$, then $w=\mathtt{a}^{i}\mathtt{b}^{j}$ for some
$i,j\geq 1$ (the words $\mathtt{a}$, $\mathtt{b}$, and the empty word, are not
synchronizing). Then, without loss of generality, if $i\leq j$ we have
$(\mathtt{b}\mathtt{a}^{j-i},\mathtt{a}),(\mathtt{b}\mathtt{a}^{j-i+1},\mathtt{ba})\in
E(w)$ but $(\mathtt{b}\mathtt{a}^{j-i},\mathtt{ba})\not\in E(w)$, hence $E(w)$
is not a cartesian product and $w$ is not synchronizing. ∎

###  7.1. Graph Presentation

In this section we discuss some properties of a graph with countable vertices
which we will eventually give a labeling in the next section. Consider the
infinite graph $G$ shown in the diagram below.

$v_{1}$$v_{2}$$v_{3}$$\cdots$$w_{1}$$w_{2}$$w_{3}$$\cdots$

We can approximate $G$ by a sequence of finite graphs $\\{G_{n}\\}_{n\geq 1}$
where $G_{n}$ is the subgraph of $G$ obtained by restricting to the set of
vertices $\\{v_{1},\dots,v_{n},w_{1},\dots,w_{n}\\}$. The adjacency matrix
$A_{n}$ corresponding to $G_{n}$ can be described recursively by

$\displaystyle A_{1}$ $\displaystyle=\begin{bmatrix}0&1\\\ 1&0\end{bmatrix}\in
M_{2}(\mathbb{N})$ $\displaystyle A_{n+1}$
$\displaystyle=\begin{bmatrix}A_{n}&\begin{matrix}0&0\\\ \vdots&\vdots\\\
0&0\\\ 0&0\\\ 0&1\end{matrix}\\\ \begin{matrix}0&\cdots&0&1&0\\\
0&\cdots&0&0&0\end{matrix}&\begin{matrix}0&0\\\
1&0\end{matrix}\end{bmatrix}\in M_{2n+2}(\mathbb{N})$

Because each $G_{n}$ is an irreducible graph, each $A_{n}$ has a unique
positive real eigenvalue equal to its spectral radius, called the Perron-
Frobenius eigenvalue of $A_{n}$, which we will denote as $\lambda_{n}$. We
will compute

$\lambda=\lim_{n\to\infty}\lambda_{n}\,.$

We must first compute the characteristic polynomial $p_{n}(t)$ for each
$A_{n}$.

######  Lemma 7.3.

For all $n\geq 1$ we have the following relation.

$\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0\\\ \vdots\\\ 0\\\
-1\end{matrix}\\\
\begin{matrix}0&\cdots&0&-1&0\end{matrix}&0\end{matrix}\right)=-1$

###### Proof.

In the case of $n=1$ it is easy to check this is true. Now assuming the
determinant in the statement of the lemma is true for some $n\geq 1$, we
compute the following using cofactor expansions

$\displaystyle\det\left(\begin{matrix}tI_{2n+2}-A_{n+1}&\begin{matrix}0\\\
\vdots\\\ 0\\\ -1\end{matrix}\\\
\begin{matrix}0&\cdots&0&-1&0\end{matrix}&0\end{matrix}\right)$
$\displaystyle=\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0&0&0\\\
\vdots&\vdots&\vdots\\\ 0&0&0\\\ 0&-1&0\end{matrix}\\\
\begin{matrix}0&\cdots&0&-1&0\\\ 0&\cdots&0&0&0\\\
0&\cdots&0&0&0\end{matrix}&\begin{matrix}t&0&0\\\ -1&t&-1\\\
-1&0&0\end{matrix}\end{matrix}\right)$
$\displaystyle=-\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0&0\\\
\vdots&\vdots\\\ 0&0\\\ -1&0\end{matrix}\\\ \begin{matrix}0&\cdots&0&-1&0\\\
0&\cdots&0&0&0\end{matrix}&\begin{matrix}0&0\\\
t&-1\end{matrix}\end{matrix}\right)$
$\displaystyle=\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0\\\
\vdots\\\ 0\\\ -1\end{matrix}\\\
\begin{matrix}0&\cdots&0&-1&0\end{matrix}&0\end{matrix}\right)$
$\displaystyle=-1\,.$

∎

######  Lemma 7.4.

For each $n\geq 1$, the characteristic polynomial $p_{n}(t)$ of the matrix
$A_{n}$ satisfies

$p_{n+1}(t)=t^{2}p_{n}(t)-1$

where $p_{1}(t)=t^{2}-1$.

###### Proof.

That $p_{1}(t)=t^{2}-1$ is clear. Then we compute via cofactor expansion

$\displaystyle p_{n+1}(t)$ $\displaystyle=\det\left(tI_{2n+2}-A_{n+1}\right)$
$\displaystyle=\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0&0\\\
\vdots&\vdots\\\ 0&0\\\ 0&-1\end{matrix}\\\ \begin{matrix}0&\cdots&0&-1&0\\\
0&\cdots&0&0&0\end{matrix}&\begin{matrix}t&0\\\
-1&t\end{matrix}\end{matrix}\right)$
$\displaystyle=t\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0\\\
\vdots\\\ 0\\\ -1\end{matrix}\\\
\begin{matrix}0&\cdots&0&0&0\end{matrix}&t\end{matrix}\right)+\det\left(\begin{matrix}tI_{2n}-A_{n}&\begin{matrix}0\\\
\vdots\\\ 0\\\ -1\end{matrix}\\\
\begin{matrix}0&\cdots&0&-1&0\end{matrix}&0\end{matrix}\right)$
$\displaystyle=t^{2}\det\left(tI_{2n}-A_{n}\right)-1$
$\displaystyle=t^{2}p_{n}(t)-1\,.$

∎

From the recursive definition of the characteristic polynomials of $A_{n}$ we
find that

$p_{n}(t)=t^{2n}-\sum_{k=0}^{n-1}t^{2k}\,.$

In particular, $\det(A_{n})=-1$ for each $n$, so each $A_{n}$ is invertible
over $\mathbb{Z}$.

Towards computing $\lambda$, we define
$q_{n}(t)=(t^{2}-1)p_{n}(t)=t^{2n+2}-2t^{2n}+1$. Note that $\lambda_{n}$ is a
solution to $q_{n}(t)$ for each $n$. Observe that the largest zero of
$q^{\prime}_{n}(t)$ is $\displaystyle t_{n}=\sqrt{\frac{2n}{n+1}}$ and that
$q^{\prime}_{n}(t)>0$ for $t>t_{n}$. Furthermore one can check that
$q_{n}(t_{n})\leq 0$ and $q_{n}(\sqrt{2})=1$ for each $n$, so since
$\lambda_{n}$ is the largest real root of $q_{n}(t)$ we must have that

$\sqrt{\frac{2n}{n+1}}\leq\lambda_{n}<\sqrt{2}$

for all $n$. Taking the limit with respect to $n$, we obtain

$\lambda=\lim_{n\to\infty}\lambda_{n}=\sqrt{2}\,.$

In the next section we will see that a labeling of the edges in $G$ gives a
presentation of the $\mathtt{a}^{n}\mathtt{b}^{n}$-shift. We conjecture that
the topological entropy of $X_{\mathtt{ab}}$, defined to be

$h(X_{\mathtt{ab}})=\lim_{n\to\infty}\frac{1}{n}\log\left(|\mathcal{L}_{n}(X_{\mathtt{ab}})|\right)\,,$

is equal to $\log(\lambda)$. However this is not in general the case for
synchronizing shifts, see [12].

###  7.2. $K$-Theory is Infinite Rank

We will show that the $K_{0}$ group of the homoclinic algebra of the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift is infinite rank. This is in contrast to
sofic shifts which have finite rank $K$-theory. This latter fact follows from
[4, Theorem 3.2.10] which says that sofic shifts have a finite number of
follower sets, and from the construction in Section 4.1. We can compute the
$K$-theory of a shift space $X$ from the Bratteli diagram $B^{\text{lc}}(X)$ —
which is itself built from follower sets.

In the case of the homoclinic algebra $A(X_{\mathtt{ab}},\sigma)$ of the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift, we will show that
$K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}$ is infinite rank. Note from
Section 4.1 that $K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}$ can be
computed as

$K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}=\varinjlim\left(\mathbb{Z}^{N_{n}},\widetilde{A}_{n}\right)$

where $\widetilde{A}_{n}$ are the transition matrices in the Bratteli diagram
$B^{\text{lc}}(X_{\mathtt{ab}})$. We will denote these transition matrices as
$\widetilde{A}_{n}$ in order to disambiguate them from the adjacency matrices
$A_{n}$ in Section 7.1.

Consider the two graphs in Figure 3. Notice that both $G_{r}$ and $G_{l}$ are
labeled versions of the graph $G$ in the previous section. The important
aspect of these graphs is that $G_{r}$ and $G_{l}$ are, respectively, _right-
resolving_ and _left-resolving_ , see [4, Section 3.3]. For $G_{r}$ (right-
resolving), this means that for each vertex there is at most a single edge out
of that vertex with a given label. Likewise for $G_{l}$ (left-resolving), each
vertex has at most a single edge into that vertex with a given label. Also see
[8, Definition 0.12] for more details.

Recall from Lemma 7.2 that a word $w$ in the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift is synchronizing if and only if $w$
contains the word $\mathtt{ba}$ as a subword. Consequently, a path which
represents a synchronizing word must thus go through $s_{r}$ on $G_{r}$ or
$s_{l}$ on $G_{l}$.

$G_{r}$:$\cdots$$s_{r}$$\cdots$$\mathtt{b}$$\mathtt{a}$$\mathtt{b}$$\mathtt{a}$$\mathtt{b}$$\mathtt{a}$$\mathtt{a}$$\mathtt{b}$$\mathtt{b}$$\mathtt{b}$$G_{l}$:$s_{l}$$\cdots$$\cdots$$\mathtt{a}$$\mathtt{a}$$\mathtt{a}$$\mathtt{a}$$\mathtt{a}$$\mathtt{a}$$\mathtt{b}$$\mathtt{b}$$\mathtt{b}$$\mathtt{b}$
Figure 3. Right-resolving and left-resolving labeled graphs for the
$\mathtt{a}^{n}\mathtt{b}^{n}$-shift.

Let $V_{r}$ and $V_{l}$ denote the set of vertices in $G_{r}$ and $G_{l}$
respectively.

######  Lemma 7.5.

Let $w$ be a synchronizing word in the $\mathtt{a}^{n}\mathtt{b}^{n}$-shift.
Then $w$ corresponds uniquely to an element of $V_{l}\times V_{r}$.

###### Proof.

Let $p_{l}$ and $p_{r}$ be paths on $G_{l}$ and $G_{r}$ respectively which
both represent the word $w$. Since $w$ is synchronizing is contains
$\mathtt{ba}$, so $w=u\mathtt{ba}v$ for some words $u$ and $v$. Observe that
the portion of $p_{l}$ representing $u\mathtt{b}$ must terminate at $s_{l}$ on
$G_{l}$, and likewise the portion of $p_{r}$ representing $\mathtt{a}v$ must
start at $s_{r}$ on $G_{r}$. Since $G_{l}$ is left-resolving, there is a
unique path representing $u\mathtt{b}$ and terminating at $s_{l}$, so there is
a unique vertex $x$ on $G_{l}$ where $p_{l}$ must initiate. Similarly, since
$G_{r}$ is right-resolving, there is a unique path representing $\mathtt{a}v$
and starting at $s_{r}$ which must terminate at a unique vertex $y$ on
$G_{r}$. Hence $w$ corresponds uniquely to the pair $(x,y)\in V_{l}\times
V_{r}$. ∎

In fact, two synchronizing word $w,v\in\mathcal{L}(X)$ are context equivalent
(see Definition 4.1) if and only if they correspond to the same element of
$V_{l}\times V_{r}$. Furthermore, we have the following result.

######  Lemma 7.6.

There is a bijective correspondence between context equivalence classes of
synchronizing words and the set $V_{l}\times V_{r}$,

###### Proof.

The correspondence in Lemma 7.5 is injective since if two words
$w,v\in\mathcal{L}(X)$ correspond to the same element of $V_{l}\times V_{r}$
then it is easy to see $E(w)=E(v)$, hence they are in the same context
equivalence class. To show it is also surjective we use the irreducibility of
the graphs $G_{l}$ and $G_{r}$. Given $x\in V_{l}$ and $y\in V_{r}$, by
irreducibility there are paths $p_{l}$ going from $x$ to $s_{l}$ and $p_{r}$
going from $s_{r}$ to $y$. Let $w$ and $v$ be the labels of $p_{l}$ and
$p_{r}$ respectively. Since $s_{l}$ only has a single in-edge labeled
$\mathtt{b}$, and $s_{r}$ only a single out-edge labeled $\mathtt{a}$, we must
have $wv=w^{\prime}\mathtt{ba}v^{\prime}$. Hence $wv$ is synchronizing and
corresponds to $(x,y)\in V_{l}\times V_{r}$. Note that $wv$ is a valid word in
the $\mathtt{a}^{n}\mathtt{b}^{n}$-shift since the follower set of the vertex
$s_{r}$ is the same as the follower set of the vertex $s_{l}$. Since $v$ is in
the follower set of $s_{r}$ and $w$ terminates at $s_{l}$, it follows that
there is a path in $G_{l}$ representing the word $wv$. ∎

Our goal is to show that $K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}$ is
infinite rank. We will now prove this.

######  Theorem 7.1.

The abelian group $K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}$ is infinite
rank.

###### Proof.

Let
$B^{\text{lc}}(X_{\mathtt{ab}})=\left(\\{V_{n}\\}_{n\geq-1},\\{E_{n}\\}_{n\geq-1}\right)$
be the Bratteli diagram constructed in Section 4.1, and let
$\widetilde{A}_{n}:\mathbb{Z}V_{n}\to\mathbb{Z}V_{n+1}$ denote the transition
matrix induced by each $E_{n}$. For $n\geq 0$, denote by
$V^{\text{sync}}_{n}\subseteq V_{n}$ the subset of vertices $v\in V_{n}$ such
that $v=[w]$ with $w$ a synchronizing word in
$\mathcal{L}_{2n+1}(X_{\mathtt{ab}})$. By the bijective correspondence in
Lemma 7.6, $V^{\text{sync}}_{n}$ can be identified with a subset of
$V_{l}\times V_{r}$. Let

$W_{2n+1}=\mathbb{Z}(V^{\text{sync}}_{n})\subseteq\mathbb{Z}\left(V_{l}\times
V_{r}\right)\cong\mathbb{Z}V_{l}\otimes\mathbb{Z}V_{r}$

denote the subspace spanned by $V^{\text{sync}}_{n}$.

Denote by $V_{l}^{n}\subseteq V_{l}$ the set of vertices
$\\{v_{1},\dots,v_{n},w_{1},\dots,w_{n}\\}$ in $G_{l}$, and likewise for
$V_{r}^{n}\subseteq V_{r}$. Then
$\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}\subseteq\mathbb{Z}V_{l}\otimes\mathbb{Z}V_{r}$.
We get a $\mathbb{Z}$-linear map
$A^{\prime}_{n}:\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}\to\mathbb{Z}V_{l}^{n+1}\otimes\mathbb{Z}V_{r}^{n+1}$
defined in terms of the matrix multiplication

$A^{\prime}_{n}(X)=A_{n}XA_{n}$

where $X\in\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}$ is a $2n$ by $2n$
matrix and $A_{n}$ are the matrices defined in Section 7.1.

Recall that $V^{\text{sync}}_{n}$ consists of equivalence classes of
synchronizing words of length $2n+1$ and that every synchronizing word must
contain the word $\mathtt{ba}$ as a subword. Hence under the bijective
correspondence in Lemma 7.6, any path representing $w$ on either of the graphs
$G_{r}$ or $G_{l}$ must also be a path on $G_{r}$ or $G_{l}$ restricted to the
vertices $V_{l}^{n}$ or $V_{r}^{n}$ respectively. Hence
$W_{2n+1}\subseteq\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}$. We will
momentarily show the image of $W_{2n+1}$ under $A^{\prime}_{n}$ satisfies

$A^{\prime}_{n}(W_{2n+1})\subseteq
W_{2n+3}\subseteq\mathbb{Z}V_{l}^{n+1}\otimes\mathbb{Z}V_{r}^{n+1}\,.$

Define $A^{\text{sync}}_{n}:W_{2n+1}\to W_{2n+3}$ to be the map
$A^{\prime}_{n}$ restricted to $W_{2n+1}$.

For each $n$, $A^{\text{sync}}_{n}$ agrees with the transition matrix
$\widetilde{A}_{n}$ restricted to
$\mathbb{Z}V^{\text{sync}}_{n}\subseteq\mathbb{Z}V_{n}$. To see this, let
$e_{ij}\in\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}$ denote the matrix
$x_{i}\otimes x_{j}$ where $1\leq i,j\leq 2n$ and $x_{i}$ and $x_{j}$ are the
$i$-th and $j$-th vertices in $V_{l}^{n}$ and $V_{r}^{n}$ respectively. Hence
the context equivalence class of a synchronizing word
$w\in\mathcal{L}_{2n+1}(X)$ can be identified uniquely with some
$e_{ij}\in\mathbb{Z}V_{l}^{n}\otimes\mathbb{Z}V_{r}^{n}$. Then since $A_{n}$
are the adjacency matrices of the underlying unlabeled graphs of $G_{r}$ and
$G_{l}$, one can see that

$A^{\prime}_{n}(e_{ij})=A_{n}e_{ij}A_{n}=\sum_{\begin{subarray}{c}(u,v)\in
E(w)\\\ |u|=|v|=1\end{subarray}}[uwv]\,.$

This inclusion $A^{\text{sync}}_{n}(W_{2n+1})\subseteq W_{2n+3}$ follows from
the fact that if $w$ is synchronizing and $(u,v)\in E(w)$ then $uwv$ is also
synchronizing.

Each $A_{n}$ has determinant $\det(A_{n})=-1$ (Lemma 7.4) and hence $A_{n}$ is
invertible over $\mathbb{Z}$ for each $n$. Hence $A^{\prime}_{n}$ is injective
onto its image: an inverse is given by the map $Y\to A_{n}^{-1}YA_{n}^{-1}$.
Consequently $A^{\prime}_{n}$ is full rank, and it follows that each
$A^{\text{sync}}_{n}$ is indeed full rank. Note that
${\text{rank}}(\widetilde{A}_{n})\geq{\text{rank}}(A^{\text{sync}}_{n})$ since
$A^{\text{sync}}_{n}$ is the restriction of $\widetilde{A}_{n}$ to
$\mathbb{Z}V^{\text{sync}}_{n}$. Furthermore, the cardinality of
$V^{\text{sync}}_{n}$ increases without bound with respect to $n$ — if this
was not true it would contradict the bijective correspondence in Lemma 7.6. In
summary, since each $A^{\text{sync}}_{n}$ is full rank, the rank of
$\widetilde{A}_{n}$ increases without bound with respect to $n$. Thus
$K_{0}\big{(}A(X_{\mathtt{ab}},\sigma)\big{)}$ has infinite rank. ∎

We remark that the proof of Theorem 7.1 also shows that
$K_{0}\big{(}\mathcal{I}_{\text{sync}}(X_{\mathtt{ab}},\sigma)\big{)}$ has
infinite rank.

##  8\. Example Related to the _GICAR_ Algebra

Let $X\subseteq\\{\mathtt{a},\mathtt{b},\mathtt{c}\\}^{\mathbb{Z}}$ be the
closure of the set of bi-infinite paths on the following graph.

…$\mathtt{a}$$\mathtt{b}$$\mathtt{b}$$\mathtt{b}$$\mathtt{c}$$\mathtt{c}$$\mathtt{c}$

This is a mixing synchronizing shift. To see it is synchronizing, note that
that a word $w\in\mathcal{L}(X)$ is sychronizing if and only if
$\mathtt{a}\sqsubseteq w$. It is also mixing by a similar argument as outlined
in Example 3.3. Furthermore, $X$ is not sofic since the words
$\\{\mathtt{ab}^{n}\mid n\geq 0\\}$ each have distinct follower sets, see [4,
Theorem 3.2.10].

The following is the Bratteli diagram $B^{\text{lcs}}_{0}(X,p)$ with respect
to the periodic point $p=\overline{\mathtt{a}}=\mathtt{...aaa.aa...}$. Note
that the vertices of $B^{\text{lcs}}_{0}(X,p)$ are in correspondence with
equivalence classes of words $w\in E^{+}(\mathtt{a})$, where $w\sim
w^{\prime}$ if and only if $|w|=|w^{\prime}|$ and
$E^{+}(\mathtt{a}w)=E^{+}(\mathtt{a}w^{\prime})$ — see Section 4.2.

$\mathtt{...aaa}$$\mathtt{a}$$\mathtt{b}$$\mathtt{a}$$\mathtt{b}$$\mathtt{ab}$$\mathtt{aa}$,
$\mathtt{bc}$$\mathtt{bb}$$\mathtt{b}$$\mathtt{a}$$\mathtt{c}$$\mathtt{b}$$\mathtt{abb}$$\mathtt{abc}$,
$\mathtt{aaa}$,$\mathtt{bca}$$\mathtt{aab}$,
$\mathtt{bcb}$,$\mathtt{bbc}$bbb$\mathtt{b}$$\mathtt{c}$$\mathtt{a}$$\mathtt{b}$$\mathtt{c}$$\mathtt{b}$$\vdots$$\vdots$$\vdots$$\vdots$

It is interesting to note that the above Bratteli diagram corresponds to an
AF-algebra called the _GICAR_ algebra, denoted $A_{\text{GICAR}}$, see [17,
Appendix]. Renault proves that,

$K_{0}(A_{\text{GICAR}})\cong\mathbb{Z}[t]$

that is, the $K$-theory of $A_{\text{GICAR}}$ is the underlying abelian group
of the ring of polynomials with integer coefficients. This isomorphism enables
a convenient description of the order structure: for $f\in
K_{0}(A_{\text{GICAR}})$, $f>0$ if and only if $f(t)>0$ for all $t\in(0,1)$.

For us however, according Theorem 4.2, $S(X,\sigma,p)$ is isomorphic to the
groupoid $C^{\ast}$-algebra of $G^{\text{lcs}}(X,\sigma,p)$, which itself has
the form

$G^{\text{lcs}}(X,\sigma,p)\cong\bigcup_{N\geq
0}G\left(B^{\text{lcs}}_{N}(X,p)\right)\,.$

Since $p=\mathtt{...aaa.aaa...}$, $B^{\text{lcs}}_{N}(X,p)$ is the same
Bratteli diagram as $B^{\text{lcs}}_{0}(X,p)$ for all $N$. Hence
$G^{\text{lcs}}(X,\sigma,p)$ is an increasing union of the above Brattli
diagram included into itself. We have discussed how the vertices of
$B^{\text{lcs}}_{0}(X,p)$, and hence $B^{\text{lcs}}_{N}(X,p)$, correspond to
equivalence classes of words in $E^{+}(\mathtt{a})$. Let $[w;N]$ denote the
vertex in $B^{\text{lcs}}_{N}(X,p)$ corresponding to the equivalence class of
the word $w$. Then the inclusion of $B^{\text{lcs}}_{N}(X,p)$ into
$B^{\text{lcs}}_{N+1}(X,p)$ sends the vertex $[w;N]$ to the vertex
$[\mathtt{a}w;N+1]$.

It is important to note that $G(B^{\text{lcs}}_{0}(X,p))$ is not in general
Morita equivalent to $G^{\text{lcs}}(X,\sigma,p)$ — we have only shown this is
true for mixing sofic shifts, see Theorem 4.3. In fact in this case, they are
not Morita equivalent. Furthermore, even though $X$ is mixing, we see in the
proof of the following lemma that $S(X,\sigma,p)$ is not simple, which is in
contrast to the mixing sofic case, see [6, Theorem 6.10].

######  Theorem 8.1.

The stable synchronizing algebra $S(X,\sigma,p)$ is not Morita equivalent to
$A_{\text{GICAR}}$.

###### Proof.

It is a fact that Morita equivalent $C^{\ast}$-algebras have isomorphic ideal
structures, see [16, Theorem 3.22]. It is mentioned in [5, Example III.5.5]
that the ideals of $A_{\text{GICAR}}$ correspond to vertices in the Bratteli
diagram $B^{\text{lcs}}_{0}(X,p)$ above. Hence ideals in $A_{\text{GICAR}}$
are in one-to-one correspondence with the vertices $[w;0]$ for $w\in
E^{+}(\mathtt{a})$. The lattice structure on $\mathcal{I}(A_{\text{GICAR}})$
is given by the edge relation on the Bratteli diagram
$B^{\text{lcs}}_{0}(X,p)$. Furthermore, each vertex $[w;N]$ corresponds to a
proper ideal in $S(X,\sigma,p)$ since $G^{0}(B^{\text{lcs}}_{N}(X,p))\cong
X^{\text{u}}(p,N)$ is an open invariant proper subset of $X^{\text{u}}(p)$,
which is identified with the unit space of $G^{\text{lcs}}(X,\sigma,p)$, see
Theorem 4.2 and [19, Proposition 4.3.2]. Note that we also identify $[w;N]$
with $[\mathtt{a}w;N+1]$.

As can be read from the Bratteli diagram $B^{\text{lcs}}_{0}(X,p)$: if
$v\sqsubseteq w$ for $v,w\in E^{+}(\mathtt{a})$, then $[w;N]\leq[v;N]$ in
$\mathcal{I}(S(X,\sigma,p))$. In particular, for $\epsilon\in
E^{+}(\mathtt{a})$ the empty word,
$[\epsilon;N]=[\mathtt{a};N+1]<[\epsilon;N+1]$ for all $N\geq 0$. Hence we
have that

$[\epsilon;0]<[\epsilon;1]<[\epsilon;2]<\dots$

is an infinite strictly ascending chain of ideals in
$\mathcal{I}(S(X,\sigma,p))$ which is bounded below. However, clearly no such
chain can exist in $\mathcal{I}(A_{\text{GICAR}})$ since there are only
finitely many vertices above a given vertex $[w;0]$ in
$B^{\text{lcs}}_{0}(X,p)$, and hence only a finite strictly ascending chain

$[w_{1}w_{2}\cdots w_{n};0]<[w_{1}w_{2}\cdots
w_{n-1};0]<\cdots<[w_{1};0]<[\epsilon;0]$

is possible, where $n=|w|$ and $w=w_{1}w_{2}\cdots w_{n}$. Hence the
respective lattices of ideals of $S(X,\sigma,p)$ and $A_{\text{GICAR}}$ cannot
be isomorphic, and it follows that they cannot be Morita equivalent.

∎

Another aspect about this example we wish to highlight is that there is an
intrinsic description of the quotient
$A(X,\sigma)/\mathcal{I}_{\text{sync}}\cong C^{\ast}(G^{\text{lc}}_{\text{non-
sync}}(X,\Sigma))$.

######  Theorem 8.2.

Let $X\subseteq\\{\mathtt{a},\mathtt{b},\mathtt{c}\\}^{\mathbb{Z}}$ defined
above. Then $G^{\text{lc}}_{\text{non-sync}}(X,\sigma)$ is defined by the
following equivalence relation. For $w\in\\{\mathtt{b},\mathtt{c}\\}^{\ast}$,
let $d(w)$ be the integer

$d(w)=|\\{i\mid 1\leq i\leq|w|,w_{i}=\mathtt{b}\\}|-|\\{j\mid 1\leq
j\leq|w|,w_{j}=\mathtt{c}\\}|\,.$

Define the equivalence relation $\sim$ on $\\{\mathtt{b},\mathtt{c}\\}^{\ast}$
by

$w\sim v\iff|w|=|v|\text{ and }d(w)=d(v)\,.$

###### Proof.

First note that $X_{\text{non-
sync}}=\\{\mathtt{b},\mathtt{c}\\}^{\mathbb{Z}}\subseteq X$, which follows
from the fact that $w\in\mathcal{L}(X)$ is synchronizing if and only if
$\mathtt{a}\sqsubseteq w$. Hence the set of _non-synchronizing words_ ,
denoted $\mathcal{L}_{\text{non-
sync}}(X)=\mathcal{L}(X)\setminus\mathcal{L}_{\text{sync}}(X)$, is exactly
$\mathcal{L}_{\text{non-sync}}(X)=\\{\mathtt{b},\mathtt{c}\\}^{\ast}$.

Next we claim that for $(x,y)\in G^{\text{lc}}(X,\sigma)$, $(x,y)$ is in
$G^{\text{lc}}_{\text{non-sync}}(X,\sigma)$ if and only if there is an $N$
such that $x_{[-N,N]}\sim y_{[-N,N]}$ and $x_{n}=y_{n}$ for all $|n|>N$. To
see this, note that since $x\sim_{\text{lc}}y$, there is an $N$ such that
$E(x_{[-N,N]})=E(y_{[-N,N]})$ and $x_{n}=y_{n}$ for $|n|>N$ — see Lemma 3.1.
Since $x_{[-N,N]},y_{[-N,N]}\in\\{\mathtt{b},\mathtt{c}\\}^{\ast}$, then it is
clear from the graph above that $E(x_{[-N,N]})=E(y_{[-N,N]})$ if and only if
$d(x_{[-N,N]})=d(y_{[-N,N]})$. ∎

The equivalence relation $\sim$ on $\\{\mathtt{b},\mathtt{c}\\}^{\ast}$ is of
interest in its own right, and is also appearing in the short exact sequence
defined in Section 4.3.

##  9\. Synchronizing Shifts from Minimal Shifts

The construction in this example demonstrates that there are synchronizing
shifts $X$ such that $X_{\text{non-sync}}$ is minimal. This construction is
essentially the same as in [12, Example 3.2].

######  Definition 9.1.

A shift space $M$ is called _minimal_ if the only $\sigma$-invariant closed
subsets of $M$ are $\emptyset$ and $M$ itself.

One can show that equivalently a shift space is minimal if the orbit
$\\{\sigma^{n}(x)\\}_{n\in\mathbb{Z}}$ is dense for every $x\in M$. In this
section we will show how to build a synchronizing shift space from an element
$m$ in a minimal shift space. Note that one can also show that forward orbit,
$\\{\sigma^{n}(x)\\}_{n\geq 0}$, is also dense in $M$ for any $x\in M$.

Let $\mathcal{A}$ be an alphabet and $M\subseteq\mathcal{A}^{\mathbb{Z}}$ a
non-trivial (i.e. not the orbit of a periodic point) minimal shift space. Fix
an element $m\in M$. Consider the following infinite graph $G(m)$ with labels
in $\widetilde{\mathcal{A}}=\mathcal{A}\sqcup\\{\mathtt{e}\\}$.

$v$$\cdots$$m_{0}$$m_{1}$$m_{2}$$\mathtt{e}$$\mathtt{e}$$\mathtt{e}$$\mathtt{e}$

The closure of the set of labeled bi-infinite paths on the above graph defines
a shift space $X(m)$ in the alphabet $\widetilde{\mathcal{A}}$. The language
of $X(m)$ is exactly the collection of words that are labels of finite paths
on the above graph.

In particular, since the forward orbit of $m$ is dense in $M$, we have
$\mathcal{L}(M)\subseteq\mathcal{L}(X(m))$. To see this, let $x_{m}\in X(m)$
be defined by

$(x_{m})_{i}=\begin{cases}m_{i}&i\geq 0\\\ \mathtt{e}&i<0\end{cases}\,.$

Then $\overline{\\{\sigma^{n}(x_{m})\\}_{n\geq 0}}=M\subseteq X(m)$. In other
words, each $w\in\mathcal{L}(M)$ occurs in
$(x_{m})_{[0,\infty)}=m_{[0,\infty)}$. Hence
$\mathcal{L}(M)\subseteq\mathcal{L}(X(m))$.

######  Theorem 9.1.

The shift space $X(m)$ is synchronizing. Furthermore, the set of non-
synchronizing points in $X(m)$ is exactly the shift space $M$.

###### Proof.

We will first show that $X(m)_{\text{non-sync}}\subseteq M$. Suppose that
$e\sqsubseteq w$, then we know that $w$ is represented by a path $q$ on $G(m)$
passing through the vertex $v$. Since any such path must pass through $v$, it
is then clear that $w$ is synchronizing by the technique used in Lemma 7.5.
Then, by minimality, since $X(m)_{\text{non-sync}}\subseteq M$ then either
$X(m)_{\text{non-sync}}=M$ or $X(m)_{\text{non-sync}}=\emptyset$. The latter
cannot be true since it would imply $X$ is a shift of finite type, which is a
contradiction — see [12, Example 3.2]. ∎

## References

  * [1] F. Blanchard and G. Hansel.  Systèmes codés.  Theoret. Comput. Sci., 44(1):17–49, 1986.
  * [2] M. Boyle, B. Kitchens, and B. Marcus.  A note on minimal covers for sofic systems.  Proc. Amer. Math. Soc., 95(3):403–411, 1985.
  * [3] O. Bratteli.  Inductive limits of finite dimensional c*-algebras.  Transactions of the American Mathematical Society, 171:195–234, 1972.
  * [4] T. J. W. I. R. Center, D. Lind, B. Marcus, L. Douglas, and M. Brian.  An Introduction to Symbolic Dynamics and Coding.  An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, 1995.
  * [5] K. Davidson.  C*-algebras by Example.  Fields Institute for Research in Mathematical Sciences Toronto: Fields Institute monographs. American Mathematical Society, 1996.
  * [6] R. J. Deeley and A. M. Stocker.  Synchronizing dynamical systems: their groupoids and $c^{*}$-algebras, 2022\.
  * [7] C. Farsi, A. Kumjian, D. Pask, and A. Sims.  Ample groupoids: equivalence, homology, and matui’s hk conjecture, 2018\.
  * [8] D. Fiebig and U.-R. Fiebig.  Covers for coded systems.  In Symbolic dynamics and its applications (New Haven, CT, 1991), volume 135 of Contemp. Math., pages 139–179. Amer. Math. Soc., Providence, RI, 1992.
  * [9] D. Fried.  Finitely presented dynamical systems.  Ergodic Theory and Dynamical Systems, 7(4):489–507, 1987.
  * [10] W. Krieger.  On sofic systems. I.  Israel J. Math., 48(4):305–330, 1984.
  * [11] H. Matui.  Homology and topological full groups of étale groupoids on totally disconnected spaces.  Proc. Lond. Math. Soc. (3), 104(1):27–56, 2012.
  * [12] K. Petersen.  Chains, entropy, coding.  Ergodic Theory Dynam. Systems, 6(3):415–448, 1986.
  * [13] I. Putnam.  _Lecture Notes on C*-Algebras_ , 01 2019.
  * [14] I. Putnam and J. Spielberg.  The structure of C*-algebras associated with hyperbolic dynamical systems.  Journal of Functional Analysis - J FUNCT ANAL, 163:279–299, 04 1999\.
  * [15] I. F. Putnam.  C*-algebras from smale spaces.  Canadian Journal of Mathematics, 48(1):175–195, 1996.
  * [16] I. Raeburn and D. Williams.  Morita Equivalence and Continuous-Trace $C*$-Algebras.  Mathematical surveys and monographs. American Mathematical Society, 1998\.
  * [17] J. Renault.  A Groupoid Approach to C*-Algebras.  Lecture Notes in Mathematics. Springer, 1980.
  * [18] J. Samuel.  C*-Algebras of Sofic Shifts.  PhD thesis, University of Victoria, 1998.
  * [19] A. Sims.  Étale groupoids and their $c^{*}$-algebras, 2018.
  * [20] S. Smale.  Differentiable dynamical systems.  Bulletin of the American Mathematical Society, 73(6):747 – 817, 1967.
  * [21] K. Thomsen.  $C^{*}$-algebras of homoclinic and heteroclinic structure in expansive dynamics.  Mem. Amer. Math. Soc., 206(970):x+122, 2010.
  * [22] P. Walters.  An Introduction to Ergodic Theory.  Graduate Texts in Mathematics. Springer New York, 1981.
  * [23] B. Weiss.  Subshifts of finite type and sofic systems.  Monatshefte für Mathematik, 77:462–474, 1973.