# Invariant measures and generalized Bratteli diagrams for substitutions on
infinite alphabets

Sergey Bezuglyi  University of Iowa, Department of Mathematics. Iowa City, IA,
52242, USA<EMAIL_ADDRESS>,  Palle E. T. Jorgensen  University of
Iowa, Department of Mathematics. Iowa City, IA, 52242, USA.  palle-
<EMAIL_ADDRESS>and  Shrey Sanadhya  Ben Gurion University of the Negev.
Department of Mathematics. Be’er Sheva, 8410501, Israel.
<EMAIL_ADDRESS>
###### Abstract.

We study substitutions on a countably infinite alphabet (without
compactification) as Borel dynamical systems. We construct stationary and non-
stationary generalized Bratteli-Vershik models for a class of such
substitutions, known as left determined. In this setting of Borel dynamics,
using a stationary generalized Bratteli-Vershik model, we provide a new and
canonical construction of shift-invariant measures (both finite and infinite)
for the associated class of subshifts.

###### Key words and phrases:

Borel dynamical systems, substitutions, infinite alphabet, Bratteli-Vershik
model, shift-invariant measures, tail invariant measures.

###### 2020 Mathematics Subject Classification:

37B10, 37A05, 37B05, 37A40, 54H05, 05C60

###### Contents

  1. 1 Introduction.
  2. 2 Preliminaries
    1. 2.1 Substitutions on infinite alphabet
    2. 2.2 Borel dynamical system
  3. 3 Left determined substitutions
  4. 4 Kakutani-Rokhlin towers for infinite substitutions.
  5. 5 Substitutions on infinite alphabet as Borel dynamical systems
    1. 5.1 Nested sequence of complete sections
  6. 6 Generalized Bratteli-Vershik models for infinite substitutions.
    1. 6.1 Generalized Bratteli diagrams
    2. 6.2 Stationary generalized Bratteli-Vershik model for substitutions on infinite alphabet
    3. 6.3 Non-stationary generalized Bratteli-Vershik model for substitutions on infinite alphabet
  7. 7 Invariant measure for infinite substitution via Bratteli diagrams
    1. 7.1 Tail invariant measure for stationary Bratteli diagrams
    2. 7.2 From tail invariant measure to shift invariant measure
  8. 8 Examples

##  1\. Introduction.

In this paper, we consider a class of substitution dynamical systems on a
countably infinite alphabet and discuss the realization of such systems by
means of generalized Bratteli diagrams. Using the Perron-Frobenius theorem for
infinite positive matrices, we describe invariant measures of substitution
dynamical systems. We present answers to the following questions in our
analysis of substitution dynamics over an infinite alphabet (a partial list):
Kakutani-Rokhlin towers for substitution dynamical systems on infinite
alphabets, stationary and non-stationary generalized Bratteli-Vershik models
for substitution dynamical systems on infinite alphabets, description of
invariant measures (both finite and $\sigma$-finite) over the path space of
the generalized Bratteli diagrams, and correspondence between tail invariant
measures to shift-invariant measures.

We recall that substitution dynamical systems, which are defined on a finite
alphabet, have been studied in many papers, and their connections with
“finite” Bratteli diagrams are well known, see the papers [DHS99], [For97],
[Dur10] for the case of minimal dynamical systems and [BKM09], [BKMS10] for
aperiodic substitutions. Roughly speaking, any nontrivial substitution
dynamical system is represented by a corresponding Vershik map acting on the
path space of a stationary Bratteli diagram.

Very few results are known about substitution dynamical systems on an infinite
alphabet. We were motivated by [Fer06] where the author carefully considered
the “square drunken man substitution” $n\to(n-2)nn(n+2),n\in{\mathbb{Z}}$.

We shall study substitution dynamical systems, stressing the dichotomy of
finite alphabet vs infinite alphabet. Recently there has been a renewed
interest in the study of dynamical systems on an infinite alphabet. In this
context, we refer to the papers on Markov shifts and substitutions: [Tak20],
[OTW14], [JKL14], [Gra11], [GS98], [RY17], [Dom12], [Fer06], [Mau06].
Dynamical systems on infinite alphabets have obvious particularities: the
underlying space is not compact. Some authors use the compactification of the
space [PFS14], [DOP18] and [MRW21]. In the current work, our focus is on the
study of substitution dynamical systems over countable infinite alphabets
without the assumption of compactification. Hence, the associated subshift
should be viewed as a Borel dynamical system (in fact, it is a homeomorphism
of a Polish space).

In the study of substitution dynamical systems over finite alphabets, the
notion of recognizability plays an important role. The term was first coined
by Martin [Mar73]. This notion has been studied by Mossé [Mos92, Mos96]. She
showed that primitive aperiodic substitutions on finite alphabets are
recognizable. Bezuglyi, Kwiatkowski, and Medynets [BKM09] extended Mossé’s
result by relaxing the requirement of primitivity. They showed that all
aperiodic substitutions on finite alphabets are recognizable. Berthé, Steiner,
Thuswaldner, and Yassawi [BSTY19] studied recognizability (and also eventual
recognizability) for sequences of morphisms that define an S-adic shift. The
notion of recognizability has been studied in word combinatorics under the
name circularity (see [Cas94, KS19, MS93]) and in the study of self-similar
tilings as unique composition property (see [Sol98]).

For substitutions over infinite alphabets, we need a property similar to
recognizability. S. Ferenczi [Fer06] introduced a notion of a left determined
substitution, which is stronger than recognizability (see Definition 3.2). In
this paper, we show that a left determined substitution admits its realization
as a Vershik map on a stationary generalized Bratteli diagram, see Definition
6.1.

Our focus on the infinite case in turn is motivated by specific applications.
First note that classes of dynamical systems arising from substitutions over a
finite alphabet have already proved to play a central role within the wider
subject dynamical systems, and more specifically in the study of symbolic
dynamics. One reason for this is the role substitution dynamics play in
diverse applications. The other reason is their amenability to use in random
walk models with specified transition matrices. The latter in turn are made
precise with the use of combinatorial diagrams, more specifically, Bratteli
diagrams; or Bratteli-Vershik diagrams.

We recall that Bratteli diagrams were first introduced by O. Bratteli in his
seminal paper [Bra72]. A Bratteli diagram is a combinatorial structure;
specifically, a graph composed of vertex levels (“levels”), and an associated
system of unoriented edges, edges between vertices having levels differing by
one: each edge only links vertices, source and range, in successive levels,
hence loops are excluded. They have turned out to provide diverse and very
powerful “models” for many mathematical structures. For example approximately
finite-dimensional $C^{*}$ algebras (also called AF-algebras), i.e., inductive
limits of systems of matrix algebras. AF-algebras are important in the field
of operator algebras and their applications to quantum physics. Moreover,
Bratteli diagrams are used in combinatorics, and in computation, for example
in an analysis of directed systems of fast Fourier transforms, arising for
example in big data models.

The first usage of Bratteli diagrams can be found in [Ver81]) (under a
different name) where the author represented any ergodic transformation of
probability measure space as a map (now known as a Vershik map) acting on the
path space of a Bratteli diagram. His work has been of immense importance as
it provides transparent models for ergodic dynamical systems. Then in 1990’s,
Giordano, Herman, Putnam and Skau (see [HPS92]; [GPS95]) and Glasner and Weiss
[GW95] successfully extended this work to minimal Cantor dynamical systems.
They constructed Bratteli-Vershik models for minimal Cantor systems. As an
application, they classified minimal Cantor systems up to orbit equivalence.
More results about applications of Bratteli diagrams for constructions of
models in Cantor dynamics can be found in [Med06], [DK19], [Shi20].

In many cases, the properties of a Bratteli diagram are determined by the
properties of incidence matrices. They show transitions between neighboring
levels. If the same incidence matrix is used at each level, then it is said
that the Bratteli diagram is stationary. A key ingredient in a systematic
study of the corresponding dynamical systems is the use of the Perron-
Frobenius theorem for the incidence matrices. As follows from the outline
above, studying substitution dynamical systems arising from countably infinite
alphabets leads to new challenges. For example, now the incidence matrices are
infinite by infinite matrices. Hence the classical Perron-Frobenius theorem
must now be adapted to infinite matrices. We use the book [Kit98] as our main
source for the Perron-Frobenius theory.

For infinite recurrent incidence matrices, the generalized Perron-Frobenius
theorem gives as a tool to find explicitly tail invariant measures (in other
words, invariant measures for substitution dynamical systems). For the
applications at hand, we show that it is possible to arrange that the
substitutions are specified by infinite but banded matrices. An infinite
banded matrix has its entries supported in a finite-width band around the
diagonal. Jacobi-matrices (used in the study of special functions) are perhaps
the best known such infinite banded matrices.

The outline of the paper is as follows. Section $2$ consists of definitions
and preliminary information regarding substitution dynamical systems on
infinite alphabets and Borel dynamics. In Section $3$, we discuss crucial
properties of left determined substitutions. In Section $4$, we construct two
versions of Kakutani-Rokhlin towers for subshifts associated with left
determined substitution on countably infinite alphabets. In Section $5$, we
study the subshift associated with left determined substitution on countably
infinite alphabets as Borel dynamical systems. Section $6$ is dedicated to the
construction of generalized Bratteli diagrams for such subshifts. In Section
$7$, using the stationary generalized Bratelli-Vershik model, we provide an
explicit formula for a shift-invariant measure. In the last section (Section
$8$), we provide some examples of substitutions on infinite alphabets,
corresponding Bratteli-Vershik models, and expression for tail-invariant
measures.

##  2\. Preliminaries

###  2.1. Substitutions on infinite alphabet

Let ${\mathcal{A}}$ be a countably infinite set, called an alphabet; its
elements are called letters. A word $w=a_{1}a_{2}\cdots a_{n}$ is a finite
string of elements in ${\mathcal{A}}$. For $n\in{\mathbb{N}}$, we denote by
${\mathcal{A}}^{n}$ the set of all words of length $n$. Then
${\mathcal{A}}^{*}=\bigcup_{n\geq 0}{\mathcal{A}}^{n}$ is the set of all words
on alphabet ${\mathcal{A}}$ including the empty word. A word $w$ is said to be
the prefix of a word $u$ if $u=ww^{\prime}$ for some word $w^{\prime}$.
Similarly, we say that $w^{\prime}$ is the suffix of $u$ if $u=ww^{\prime}$.
We denote by ${\mathcal{A}}^{\mathbb{Z}}$ the set of all bi-infinite sequence
$(x_{i})_{i\in{\mathbb{Z}}}$ over ${\mathcal{A}}$ and endow it with the
topology induced by the metric:

$d(x,y):=2^{-\textrm{inf}\,\\{|i|:\,\,x_{i}\,\neq\,y_{i}\\}}\,\,\mathrm{for}\,\,x,y\in{\mathcal{A}}^{{\mathbb{Z}}}.$
(2.1)

Then the topological space $({\mathcal{A}}^{\mathbb{Z}},d)$ is a zero-
dimensional Polish space. A word $w=a_{1}a_{2}\cdots a_{n}$ is said to occur
at the $j$-th place in the infinite sequence
$x\in{\mathcal{A}}^{{\mathbb{Z}}}$ if $x_{j}=a_{1},...,x_{j+n-1}=a_{n}$. In
this case, we also say that $w$ is a factor of $x$. Similarly, we will denote
by $x_{[p,q]}$ ; $p,q\in{\mathbb{Z}}$ , $q>p$, the word of length $q-p+1$
occurring at $p$-th place in $x$. Given an infinite word
$x\in{\mathcal{A}}^{{\mathbb{Z}}}$, let ${\mathcal{L}}_{n}(x)$ denote the set
of all factors of $x$ of length $n$. Then the language ${\mathcal{L}}(x)$ of
$x$ is the set of all factors of $x$, i.e.,
${\mathcal{L}}(x)=\underset{n\in{\mathbb{N}}}{\bigcup}{\mathcal{L}}_{n}(x)$.

######  Definition 2.1.

A substitution $\sigma$ on a countably infinite set ${\mathcal{A}}$ is an
injective map from ${\mathcal{A}}$ to ${\mathcal{A}}^{+}$ (the set of non-
empty finite words on ${\mathcal{A}}$), which associates to every letter $a\in
A$ a finite word $\sigma(a)\in{\mathcal{A}}^{+}$. The length of $\sigma(a)$ is
denoted by $h_{a}:=|\sigma(a)|$. We assume that $h_{a}\geq 2$ for all
$a\in{\mathcal{A}}$.

For a substitution $\sigma:{\mathcal{A}}\to{\mathcal{A}}^{+}$, the infinite
matrix $M=(m_{ab})$, $a,b\in{\mathcal{A}}$, where $m_{ab}$ is the number of
occurrences of the letter $b$ in the word $\sigma(a)$, is called the
substitution matrix of $\sigma$.

We extend the substitution $\sigma$ to ${\mathcal{A}}^{*}$ by concatenation,
i.e., for $w=a_{1}a_{2}\cdots a_{n}\in{\mathcal{A}}^{+}$, put
$\sigma(w)=\sigma(a_{1})\sigma(a_{2})\cdots\sigma(a_{n})$ (and for empty word
$\emptyset$, put $\sigma(\emptyset)=\emptyset$). We iterate the substitution
$\sigma$ on ${\mathcal{A}}$ in the usual way by putting
$\sigma^{i}=\sigma\circ\sigma^{i-1}$.

######  Remark 2.2.

(1) We included in Definition 2.1 two properties of a substitution $\sigma$:
injectivity on letters and growth of word length, $|\sigma^{n}(a)|\geq 2^{n}$.
In other words, we consider a class of substitutions on ${\mathcal{A}}$
satisfying these properties. This assumption is made in order to avoid some
pathological cases. It will be clear from our main results why we need these
assumptions.

(2) The fact that ${\mathcal{A}}$ is an infinite alphabet gives more
possibilities to consider various properties of substitutions $\sigma$ on
${\mathcal{A}}$ in comparison with substitutions on a finite alphabet.
Conversely, some properties of finite substitutions cannot be defined for
substitutions on infinite alphabets. In particular, there are no primitive
substitutions on an infinite alphabet assuming the finiteness of words.

In the definition below, we introduce a class of substitutions of bounded
size. This definition makes the behavior of $\sigma$ more predictable.

In some cases, it is convenient to identify the set ${\mathcal{A}}$ with the
set of integers ${\mathbb{Z}}$ or the set of natural numbers ${\mathbb{N}}$.

######  Definition 2.3.

We say that $\sigma$ is of bounded length if there exists an integer $L\geq 2$
such that for every $a\in{\mathcal{A}}$, $|\sigma(a)|\leq L$. In the case
when, for every $a\in A$, $|\sigma(a)|=L$, we say that $\sigma$ is of constant
length.

Identifying ${\mathcal{A}}$ with ${\mathbb{Z}}$, we say that
$\sigma:n\to\sigma(n)$, $n\in{\mathbb{Z}}$ is of bounded size, if it is of
bounded length and there exists a positive integer $t$ (independent of $n$)
such that for every $n\in{\mathbb{Z}}$, if $m\in\sigma(n)$, then
$m\in\\{n-t,...,n,...,n+t\\}$. We call $t\in{\mathbb{N}}$ the size of $\sigma$
where $t$ is taken minimal possible.

######  Remark 2.4.

Note that if $\sigma$ is of bounded length (respectively, of constant length),
then the corresponding substitution matrix $M$ has bounded row sum property
(respectively, equal row sum property). If $\sigma$ is of bounded size, then
the substitution matrix $M$ is a band matrix (i.e., non-zero entries are
confined to a diagonal band of width $2t+1$), and it has bounded row sum
property.

The left shift
$T:{\mathcal{A}}^{\mathbb{Z}}\rightarrow{\mathcal{A}}^{\mathbb{Z}}$ is defined
by $(Tx)_{k}=x_{k+1}$ for all $k\in{\mathbb{Z}}$. Recall that a subshift
$(X,T)$ is a dynamical system where $X$ a closed shift-invariant subset of
${\mathcal{A}}^{{\mathbb{Z}}}$. We define the language ${\mathcal{L}}_{X}$ of
a subshift $(X,T)$ as ${\mathcal{L}}_{X}=\underset{x\in
X}{\bigcup}{\mathcal{L}}(x)$. On the other hand, let ${\mathcal{L}}$ be a set
of finite words on a countably infinite alphabet ${\mathcal{A}}$ that is
closed under taking subwords. We denote by $X_{{\mathcal{L}}}$ the set of bi-
infinite sequences such that all their subwords belong to ${\mathcal{L}}$.
This defines a subshift $(X_{{\mathcal{L}}},T)$ which is called the subshift
associated with ${\mathcal{L}}$. Interesting examples of such languages are
generated using substitutions as defined below.

######  Definition 2.5.

We define the language of a substitution $\sigma$ on a countably infinite
alphabet ${\mathcal{A}}$ by setting

${\mathcal{L}}_{\sigma}=\\{\textrm{factors of }\sigma^{n}(a):\ \textrm{for
some}\,\,n\geq 0,\ a\in{\mathcal{A}}\\}.$

For $n\in{\mathbb{N}}$, we will denote by ${\mathcal{L}}_{\sigma}(n)$ all
words of length $n$ in the language ${\mathcal{L}}_{\sigma}$. Consider the
subset
$X_{\sigma}:=\\{x\in{\mathcal{A}}^{\mathbb{Z}}:{\mathcal{L}}(x)\subset{\mathcal{L}}_{\sigma}\\}\subset{\mathcal{A}}^{\mathbb{Z}}$.
Then $X_{\sigma}$ is a closed subset of ${\mathcal{A}}^{{\mathbb{Z}}}$ which
is invariant with respect to $T$. We call $(X_{\sigma},T)$ the subshift on
${\mathcal{A}}$ associated with the substitution $\sigma$ or a substitution
dynamical system.

Every finite word $\overline{x}=(x_{m},...,x_{n})$, where $m\leq
n\in{\mathbb{Z}}$, determines a cylinder set $[\overline{x}]_{(m,n)}$ in
$X_{\sigma}$ of length $n-m+1$ :

$[\overline{x}]_{(m,n)}:=\\{y=(y_{i})\in
X_{\sigma}:y_{m}=x_{m},...,y_{n}=x_{n}\\}.$ (2.2)

The zero-dimensional topology on $X_{\sigma}$ inherited from
${\mathcal{A}}^{{\mathbb{Z}}}$ is generated by the collection of all cylinder
sets. Note that these cylinder sets also generate the $\sigma$-algebra111The
letter $\sigma$ used here is a traditional notation which is not related to a
substitution $\sigma$. of Borel sets in $X_{\sigma}$. Later, we will work with
cylinder sets of the form $[\overline{x}]_{(0,n)}$, $n\in{\mathbb{N}}_{0}$, of
length $n+1$

$[\overline{x}]_{(0,n)}:=\\{y=(y_{i})\in
X_{\sigma}:y_{0}=x_{0},...,y_{n}=x_{n}\\}.$ (2.3)

For simplicity, when $n$ is known by context we will denote
$[\overline{x}]_{(0,n)}$ by $[\overline{x}]$.

###  2.2. Borel dynamical system

In Section 5, we will interpret the subshift on a countably infinite alphabet
as a Borel dynamical system. Below we provide some definitions from Borel
dynamics and descriptive set theory.

Let $X$ be a separable completely metrizable topological space (also called a
Polish space), and let ${\mathcal{B}}$ be the $\sigma$-algebra of Borel sets
generated by open sets in $X$. Then the pair $(X,{\mathcal{B}})$ is called a
standard Borel space. Any two uncountable standard Borel spaces are Borel
isomorphic.

For a standard Borel space $(X,{\mathcal{B}})$, a one-to-one Borel map $T$ of
$X$ onto itself is called a Borel automorphism of $(X,{\mathcal{B}})$. Let
$Aut(X,{\mathcal{B}})$ denote the group of all Borel automorphisms of
$(X,{\mathcal{B}})$. Any subgroup $\Gamma$ of $Aut(X,\mathcal{B})$ is called a
Borel automorphism group, and the pair $(X,\Gamma)$ is referred to as a Borel
dynamical system. In this paper, we will only work with groups $\Gamma$
generated by a single automorphism $T$ of $(X,{\mathcal{B}})$. A Borel
automorphism is called free if $Tx\neq x$ for every $x\in X$. If the orbit
$Orb_{T}(x)=\\{T^{n}x:n\in{\mathbb{Z}}\\}$ is infinite for every $x$, then $T$
is called aperiodic.

An equivalence relation $E$ on $(X,\mathcal{B})$ is called Borel if $E$ is a
Borel subset of the product space $X\times X$. It is said that an equivalence
relation $E$ on $(X,\mathcal{B})$ is a countable equivalence relation (CBER)
(or aperiodic) if the equivalence class $[x]_{E}:=\\{y\in X:(x,y)\in E\\}$ is
countable for every $x\in X$. Let $B\in{\mathcal{B}}$ be a Borel set, then the
saturation of $B$ with respect to a CBER $E$ on $(X,{\mathcal{B}})$ is the set
$[B]_{E}$ containing entire equivalence classes $[x]_{E}$ for every $x\in B$.

In the study of Borel dynamical systems, the theory of countable Borel
equivalence relations on $(X,\mathcal{B})$ plays an important role as it
provides a link between descriptive set theory and Borel dynamics (see Theorem
2.6 below). We refer the reader to [Kec19] for an up-to-date survey of the
theory of countable Borel equivalence relations. We refer to [DJK94], [BK96],
[Kec95], [Hjo00], [JKL02], [KM04], [Nad13], [Var63], and [Wei84], where the
reader can find connections between the study of orbit equivalence in the
context of dynamical systems and descriptive set theory.

Let $\Gamma\subset Aut(X,{\mathcal{B}})$ be a countable Borel automorphism
group of $(X,{\mathcal{B}})$. Then the orbit equivalence relation
$E_{X}(\Gamma)$ generated by $\Gamma$ on $X$ is

$E_{X}(\Gamma)=\\{(x,y)\in X\times X:x=\gamma y\ \mbox{for\ some}\
\gamma\in\Gamma\\}.$

The following theorem shows that all CBERs come from Borel actions of
countable groups.

######  Theorem 2.6 (Feldman–Moore [FM77]).

Let $E$ be a countable Borel equivalence relation on a standard Borel space
$(X,\mathcal{B})$. Then there is a countable group $\Gamma$ of Borel
automorphisms of $(X,\mathcal{B})$ such that $E=E_{X}(\Gamma)$.

######  Definition 2.7.

A Borel set $C$ is called a complete section for an equivalence relation $E$
on $(X,{\mathcal{B}})$ if every $E$-class intersects $C$. In other words,
$[C]_{E}=X$.

We can also interpret this definition in terms of a Borel automorphism as
follows: given $T\in Aut(X,{\mathcal{B}})$, a Borel set $C\subset X$ is called
a complete section (or simply a $T$-section) if every $T$-orbit meets $C$ at
least once. In other words, $X=\underset{i\in{\mathbb{Z}}}{\bigcup}\,T^{i}C$.

##  3\. Left determined substitutions

Let $\sigma$ be a substitution on ${\mathcal{A}}$ as in Definition 2.1. Then
$\sigma$ defines a map, $\sigma:X_{\sigma}\to X_{\sigma}$ where, for
$x=(x_{i})\in X_{\sigma}$, one takes $\sigma(x)=(\sigma(x_{i}))$. We use the
same notation $\sigma$ for the map defined on $X_{\sigma}$. It will be clear
from the context whether we consider the substitution or the above map. We
recall the definition of recognizability.

######  Definition 3.1.

Let $\sigma$ be a substitution on a countably infinite alphabet
${\mathcal{A}}$ satisfying Definition 2.1. Let $(X_{\sigma},T)$ be the
corresponding subshift. It is said that $\sigma$ is recognizable if for each
$x=(x_{i})_{i\in{\mathbb{Z}}}\in X_{\sigma}$ there exists a unique
$y=(y_{i})_{i\in{\mathbb{Z}}}\in X_{\sigma}$ and unique
$k\in\\{0,...,|\sigma(y_{0})|-1\\}$ such that

$x=T^{k}\sigma(y).$ (3.1)

For the study of substitutions over countable infinite alphabets, Ferenczi
[Fer06] coined the notion of a left determined substitution (Definition 3.2).
This notion is stronger than recognizability, and it will be a key notion of
the current work. We will show below that a left determined substitution is
recognizable (see Corollary 3.4).

######  Definition 3.2 ([Fer06]).

A substitution $\sigma$ on a countably infinite alphabet ${\mathcal{A}}$ is
called left determined if there exists $N_{\sigma}\in{\mathbb{N}}$ (minimal
possible) such that any word $w\in{\mathcal{L}}_{\sigma}$ of length at least
$N_{\sigma}$ has a unique decomposition $w=w_{1}w_{2}\cdots w_{s}$ such that
each $w_{i}=\sigma(a_{i})$ for some unique $a_{i}\in{\mathcal{A}}$, except
that $w_{1}$ may be a suffix of $\sigma(a_{1})$ and $w_{s}$ may be a prefix of
$\sigma(a_{s})$. We will call this decomposition of a word $w$ the unique
$\sigma$-decomposition of $w$.

For example, it was shown in [Fer06] that the squared drunken man substitution

$n\mapsto(n-2)\,n\,n\,(n+2),\,\,n\in 2{\mathbb{Z}},\ $

is left determined: any word of length at least $3$ has a unique
$\sigma$-decomposition. We will give more examples of left determined
substitutions in Section 8.

For this new and more general framework, our first result below shows that
every left determined substitution has a natural realization as a
homeomorphism of a metric space.

######  Theorem 3.3.

Let $\sigma$ be a left determined substitution on a countably infinite
alphabet ${\mathcal{A}}$, then $\sigma$ is a homeomorphism from $X_{\sigma}$
to $\sigma(X_{\sigma})$.

###### Proof.

Note that by definition, $\sigma:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is
injective and $\sigma(X_{\sigma})\subset X_{\sigma}$. To see that the map
$\sigma:X_{\sigma}\rightarrow X_{\sigma}$ is injective, we assume that there
are distinct $x,y\in X_{\sigma}$ such that $\sigma(x)=\sigma(y)=z\in
X_{\sigma}$. Consider the word $w$ of length $2\ell+1\geq N_{\sigma}$ given by
$w=z_{-\ell}\cdots z_{0}\cdots z_{\ell}$ where $z=(z_{i})$. Since $\sigma$ is
left determined, $w$ has the unique $\sigma$-decomposition of the form

$w=w_{-p}w_{-p+1}\cdots w_{0}\cdots
w_{s-1}w_{s}=w_{-p}\sigma(a_{-p+1})\cdots\sigma(a_{0})\cdots\sigma(a_{s-1})w_{s}$

where $a_{j}\in{\mathcal{A}}\,,\,j\in\\{-p,...,0,...,s\\}$, and $p,s$ are
positive integers. Here we chose the labeling $\\{-p,...,0,...,s\\}$ such that
$z_{0}\in\sigma(a_{0})$. Also, $w_{-p}$ and $w_{s}$ are either empty words or
a suffix of $\sigma(a_{-p})$ and a prefix of $\sigma(a_{s})$, respectively.
Since the finite word $w$ has length at least $N_{\sigma}$, any extension
$w^{\prime}$ of $w$ will also have a unique $\sigma$-decomposition that does
not change the word
$\sigma(a_{-p+1})\cdots\sigma(a_{0})\cdots\sigma(a_{s-1})$. Continuing this
procedure, we conclude that $z$ (as a bi-infinite extension of $w$) also has a
unique $\sigma$-decomposition. In other words, there exists unique
$u=(a_{i})_{i\in{\mathbb{Z}}}$, such that $\sigma(u)=z$. Since $\sigma$ is
injective on letters from ${\mathcal{A}}$, we conclude that $x=u=y$. This
proves that $\sigma:X_{\sigma}\rightarrow X_{\sigma}$ is injective.

The continuity of $\sigma$ is obvious. To see that $\sigma^{-1}$ is continuous
observe that, for $j\in{\mathbb{N}}$, if $\sigma(x)$ and $\sigma(y)$ agree on
a cylinder set of length at least $2j$ (say $[c]_{(p,p+2j-1)}$ for some
$p\in{\mathbb{Z}}$), then $x,y$ agree on a cylinder set of length $j$ (say
$[c^{\prime}]_{(q,q+j-1)}$ for some $q\in{\mathbb{Z}}$). This claim follows
from the fact that if a word $w$ admits a unique $\sigma$-decomposition
$w=w_{1}\sigma(a_{2}\cdots a_{s-1})w_{s}$, then the length of $a_{2}\cdots
a_{s-1}$ tends to infinity as $|w|\to\infty$. ∎

The following is a direct corollary of Theorem 3.3.

######  Corollary 3.4.

If $\sigma$ is left determined substitution on a countably infinite alphabet
${\mathcal{A}}$, then $\sigma$ is recognizable.

###### Proof.

Since $\sigma$ is injective for each $x=(x_{i})_{i\in{\mathbb{Z}}}\in
X_{\sigma}$, there exists a unique $y=(y_{i})_{i\in{\mathbb{Z}}}\in
X_{\sigma}$ and such that $x=\sigma(y)$. Thus, $\sigma$ satisfies (3.1) for
$k=0$. ∎

Recall that we consider only injective substitutions
$\sigma:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$. In general, $\sigma^{n}$
needs not be injective. However, the following proposition shows that, for
left determined substitutions, $\sigma^{n}$ is also injective for all
sufficiently large $n$. Our next result offers an explicit and uniform
estimate on word length for powers of a general left determined substitution.

######  Theorem 3.5.

Let $\sigma$ be a left determined substitution on a countably infinite
alphabet ${\mathcal{A}}$. Then, for all $k\in{\mathbb{N}}$ such that
$2^{k-1}\geq N_{\sigma}$, the map
$\sigma^{k}:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is injective.

###### Proof.

Given a left determined substitution $\sigma$, fix a natural number
$N_{\sigma}$ such that all words of length at least $N_{\sigma}$ admit unique
$\sigma$-decompositions. We show that the map

$\sigma:\underset{n\geq
N_{\sigma}}{\bigcup}{\mathcal{L}}_{\sigma}(n)\rightarrow{\mathcal{A}}^{+}$
(3.2)

is injective. To see this, assume that there exist distinct
$w_{1},w_{2}\in\underset{n\geq N_{\sigma}}{\bigcup}{\mathcal{L}}_{\sigma}(n)$
such that

$\sigma(w_{1})=\sigma(w_{2})=:w.$ (3.3)

Since $|w_{1}|,|w_{2}|\geq N_{\sigma}$, we have $|w|>N_{\sigma}$. Hence, $w$
must have a unique $\sigma$-decomposition, which contradicts (3.3).

Next, we show that, for all $k\in{\mathbb{N}}$ such that $2^{k-1}\geq
N_{\sigma}$, the map $\sigma^{k}:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is
injective. Assume for the contrary that there exist
$a_{1},a_{2}\in{\mathcal{A}}$ such that $a_{1}\neq a_{2}$ but

$\sigma^{k}(a_{1})=\sigma^{k}(a_{2})=:\bar{w}.$ (3.4)

We write (3.4) as

$\sigma(\sigma^{k-1}(a_{1}))=\sigma(\sigma^{k-1}(a_{2}))=:\bar{w}.$ (3.5)

Note that for every $a\in{\mathcal{A}}$, $|\sigma(a)|\geq 2$, implies
$|\sigma^{k-1}(a)|\geq 2^{k-1}\geq N_{\sigma}$. Thus, injectivity of the map
in (3.2) contradicts (3.5). Hence, the map
$\sigma^{k}:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is injective. ∎

######  Theorem 3.6.

Let $\sigma$ be a bounded length substitution on a countably infinite alphabet
${\mathcal{A}}$ and
$C=\mathrm{max}\,\,\\{|\sigma(a)|\,;\,\,a\in{\mathcal{A}}\\}$. If $\sigma$ is
left determined, then $\sigma^{n}$ is also left determined for all $n>1$, and
$N_{\sigma^{n}}$ can be chosen as $N_{\sigma}C^{n-1}$.

###### Proof.

First we prove the theorem for $n=2$. Let $w$ be a word of length at least
$N_{\sigma}C$, where $N_{\sigma}$ is as in Definition 3.2. We will show that
$w$ has a unique representation of the form

$w=p_{1}\sigma^{2}(b_{2})\cdots\sigma^{2}(b_{\ell-1})p_{\ell}\,;\,b_{j}\in{\mathcal{A}}\,,\,j\in\\{1,2,...,\ell\\},$

where $p_{1}$ and $p_{\ell}$ are either empty words or suffix of
$\sigma^{2}(b_{1})$ and prefix of $\sigma^{2}(b_{\ell})$, respectively. Since
$\sigma$ is left determined and $|w|>N_{\sigma}$, the word $w$ has a unique
representation of the form

$w=w_{1}\cdots
w_{s}=w_{1}\sigma(a_{2})\cdots\sigma(a_{s-1})w_{s}\,;\,a_{i}\in{\mathcal{A}}\,,\,i\in\\{1,2,...,s\\},$
(3.6)

where $w_{1}$ and $w_{s}$ are either empty words or suffix of $\sigma(a_{1})$
and prefix of $\sigma(a_{s})$, respectively. We consider the case when $w_{1}$
and $w_{s}$ are both non-empty words (other cases are easier and can be
similarly proved).

We claim that relation (3.6) implies $s\geq N_{\sigma}$. To see this, assume
towards a contradiction that $s<N_{\sigma}$. Note that for
$i\in\\{2,...,s-1\\}$, $2\leq|\sigma(a_{i})|\leq C$ and for $i\in\\{1,s\\}$,
$1\leq|\sigma(a_{i})|<C$. These inequalities imply that $|w|<sC<N_{\sigma}C$,
which is a contradiction because we took $w$ such that $|w|\geq N_{\sigma}C$.

Let

$\sigma(a_{1})=a_{(1,1)}a_{(1,2)}\cdots a_{(1,m)},\,\textrm{where}\,\,\,2\leq
m\leq C$

and

$\sigma(a_{s})=a_{(s,1)}a_{(s,2)}\cdots a_{(s,n)},\,\textrm{where}\,\,\,2\leq
n\leq C.$

Since $w_{1}$ is suffix of $\sigma(a_{1})$ and $w_{2}$ is prefix of
$\sigma(a_{s})$, we have

$w_{1}=a_{(1,t)}\cdots a_{(1,m)},\,\textrm{for some}\,\,\,t\in\\{2,...,m\\}$

and

$w_{s}=a_{(s,1)}\cdots a_{(s,r)},\,\textrm{for
some}\,\,\,r\in\\{1,...,n-1\\}.$

Thus, we can rewrite (3.6) as follows

$w=a_{(1,t)}\cdots a_{(1,m)}\sigma(a_{2}\cdots a_{s-1})a_{(s,1)}\cdots
a_{(s,r)}.$

We complete the suffix (i.e. $w_{1}$) and prefix (i.e. $w_{s}$) to get the
word $w^{\prime}$ from $w$ as follows:

$w^{\prime}=a_{(1,1)}\cdots a_{(1,t-1)}a_{(1,t)}\cdots
a_{(1,m)}\sigma(a_{2}\cdots a_{s-1})a_{(s,1)}\cdots a_{(s,r)}a_{(s,r+1)}\cdots
a_{(s,n)}$ (3.7) $=\sigma(a_{1})\sigma(a_{2}\cdots
a_{s-1})\sigma(a_{s})=\sigma(a_{1}\cdots a_{s}).$

Since $s\geq N_{\sigma}$ and $\sigma$ is left determined, the word
$a_{1}\cdots a_{s}$ has the unique representation of the form

$a_{1}\cdots a_{s}=u_{1}u_{2}\cdots
u_{\ell-1}u_{\ell}=u_{1}\sigma(b_{2})\cdots\sigma(b_{\ell-1})u_{\ell},\,;\,b_{j}\in{\mathcal{A}}\,,\,j\in\\{1,2,...,\ell\\}$
(3.8)

where $u_{1}$ and $u_{\ell}$ are either empty words or suffix of
$\sigma(b_{1})$ and prefix of $\sigma(b_{\ell})$ respectively. Again we will
consider the case when $u_{1}$ and $u_{\ell}$ are both non-empty words. We
have by (3.8)

$w^{\prime}=\sigma(a_{1}\cdots
a_{s})=\sigma(u_{1}\sigma(b_{2})\cdots\sigma(b_{\ell-1})u_{\ell})$

Let $u_{1}=a_{1}a_{2}\cdots a_{k_{1}}$ for some $k_{1}\in\\{1,...,s\\}$.
Similarly, let $u_{\ell}=a_{k_{2}}a_{k_{2}+1}\cdots a_{s}$ for some
$k_{2}\in\\{1,...,s\\}$. Since $u_{1}$ is a suffix of $\sigma(b_{1})$,
$\sigma(a_{1}a_{2}\cdots a_{k_{1}})=\sigma(u_{1})$ is the suffix of
$\sigma^{2}(b_{1})$. It follows from (3.7) that

$a_{(1,1)}\cdots a_{(1,t-1)}a_{(1,t)}\cdots
a_{(1,m)}\sigma(a_{2})\cdots\sigma(a_{k_{1}})$ is a suffix of
$\sigma^{2}(b_{1})$.

Hence,

$p_{1}:=a_{(1,t)}\cdots a_{(1,m)}\sigma(a_{2})\cdots\sigma(a_{k_{1}})$ is a
suffix of $\sigma^{2}(b_{1})$.

Similarly, since $u_{\ell}$ is a prefix of $\sigma(b_{\ell})$, the word
$\sigma(a_{k_{2}}a_{k_{2}+1}\cdots a_{s})=\sigma(u_{\ell})$ is a prefix of
$\sigma^{2}(b_{\ell})$. Relation (3.7) implies that

$\sigma(a_{k_{2}})\sigma(a_{k_{2}+1})\cdots\sigma(a_{s-1})a_{(s,1)}\cdots
a_{(s,r)}a_{(s,r+1)}\cdots a_{(s,n)}$ is a prefix of $\sigma^{2}(b_{\ell})$.

Hence,

$p_{\ell}:=\sigma(a_{k_{2}})\sigma(a_{k_{2}+1})\cdots\sigma(a_{s-1})a_{(s,1)}...a_{(s,r)}$
is a prefix of $\sigma^{2}(b_{\ell})$.

Thus, we get

$w=p_{1}\sigma^{2}(b_{2})\cdots\sigma^{2}(b_{\ell-1})p_{\ell}$

as needed. We proved that every word of length at least $N_{\sigma}C$ has a
unique $\sigma$-decomposition. The proof for $n>2$ is similar. ∎

##  4\. Kakutani-Rokhlin towers for infinite substitutions.

In this section, we construct Kakutani-Rokhlin (K-R) towers for subshifts
associated with left determined substitutions on countably infinite alphabets.
The bases of K-R towers in our construction are represented by cylinder sets.
We give two versions of K-R towers based on the structure of cylinder sets
that form the bases of the towers. These constructions are central to our work
as they form building blocks for Bratteli-Vershik models of the corresponding
subshifts.

Recall that for a finite word $\overline{x}=(x_{0},...,x_{n})$,
$[\overline{x}]$ denotes the cylinder set of the form
$[\overline{x}]_{(0,n)}$, $n\in{\mathbb{N}}_{0}$ (see (2.3)). We should
mention that Theorem 4.1 below is a generalization of Lemma $2.8$ from
[Fer06], where the author worked with the squared drunken man substitution
which has constant length.

######  Theorem 4.1.

Let $\sigma$ be a bounded length left determined substitution on a countably
infinite alphabet ${\mathcal{A}}$, and let $(X_{\sigma},T)$ be the
corresponding subshift. Then, for any $n\in{\mathbb{N}}$, there exists a
partition of $X_{\sigma}$ into Kakutani-Rokhlin towers given by

$X_{\sigma}=\underset{a\in{\mathcal{A}}}{\bigsqcup}\,\,\,\underset{k=0}{\overset{h^{(n)}_{a}-1}{\bigsqcup}}\,T^{k}[\sigma^{n}(a)]$
(4.1)

where $h^{(n)}_{a}=|\sigma^{n}(a)|$, $a\in{\mathcal{A}}$.

###### Proof.

First, we prove this theorem for $n=1$. Since $\sigma$ is left determined,
there exists $N_{\sigma}\in{\mathbb{N}}$ such that every word of length
greater than or equal to $N_{\sigma}$ has a unique decomposition. If
$N_{\sigma}$ is odd, put $\ell=\dfrac{N_{\sigma}-1}{2}$, otherwise put
$\ell=\dfrac{N_{\sigma}}{2}$. We take arbitrary $x$ in $X_{\sigma}$ and show
that there exists $a\in{\mathcal{A}}$ such that

$x\in\underset{k=0}{\overset{h_{a}-1}{\bigsqcup}}\,T^{k}[\sigma(a)].$

For $x=\\{x_{i}\\}_{i\in{\mathbb{Z}}}\in X_{\sigma}$, consider the word
$w=x_{-\ell}\cdots x_{0}\cdots x_{\ell}$ of length $2\ell+1=N_{\sigma}$. Since
$\sigma$ is left determined, $w$ has a unique representation of the form

$w=w_{-p}w_{-p+1}\cdots w_{0}\cdots
w_{s-1}w_{s}=w_{-p}\sigma(a_{-p+1})\cdots\sigma(a_{0})\cdots\sigma(a_{s-1})w_{s}$
(4.2)

for $a_{j}\in{\mathcal{A}}\,,\,j\in\\{-p,...0...,s\\}$, where $p,s$ are
positive integers. Here we choose the labeling $\\{-p,...0...,s\\}$ such that
$x_{0}\in\sigma(a_{0})$. Also, by definition of a left determined
substitution, $w_{-p}$ and $w_{s}$ are either empty words or suffix of
$\sigma(a_{-p})$ and prefix of $\sigma(a_{s})$, respectively.

We denote $h_{0}:=h_{a_{0}}=|\sigma(a_{0})|$ and set
$\sigma(a_{0})=b_{1}\cdots b_{h_{0}}$, where $b_{i}\in{\mathcal{A}}$ for
$i\in\\{1,...,h_{0}\\}$. By uniqueness of the representation in (4.2), $a_{0}$
is uniquely determined. Also $x_{0}=b_{j}$ for some $j\in\\{1,...,h_{0}\\}$.
We define

$y=(y_{i}),\,y_{i}=x_{i-(j-1)},\,\mathrm{for}\,\mathrm{all}\,\,i\in{\mathbb{Z}}.$

Set $j-1=k$, then $T^{-k}x=y$. Since $y\in[\sigma(a_{0})]$, we obtain that
$x\in T^{k}[\sigma(a_{0})]$ for some $k\in\\{0,...,h_{0}-1\\}$. Hence, we have

$X_{\sigma}=\underset{a\in{\mathcal{A}}}{\bigsqcup}\,\,\,\underset{k=0}{\overset{h_{a}-1}{\bigsqcup}}\,T^{k}[\sigma(a)]$
(4.3)

where $h_{a}=|\sigma(a)|$, for $a\in{\mathcal{A}}$. We claim that the two
unions in (4.3) are disjoint. To see this assume that the first union is not
disjoint. Hence there exists $x\in X_{\sigma}$ such that $x\in
T^{k_{i}}[\sigma(a_{i})]\cap T^{k_{j}}[\sigma(a_{j})]$ for $a_{i}\neq
a_{j}\in{\mathcal{A}}$, $k_{i}\in\\{0,...,h_{a_{i}}-1\\}$ and
$k_{j}\in\\{0,...,h_{a_{j}}-1\\}$. This implies that the word
$w=x_{-\ell}\cdots x_{0}\cdots x_{\ell}$ has two different decompositions (of
the form (4.2)) one with $a_{0}=a_{i}$ and another with $a_{0}=a_{j}$. This
contradicts the fact that $\sigma$ is left determined. Similarly, assume that
the second union in (4.3) is not disjoint. Hence there exists $x\in
X_{\sigma}$ such that $x\in T^{k_{i}}[\sigma(a)]\cap T^{k_{j}}[\sigma(a)]$,
for $k_{i}\neq k_{j}\in\\{0,...,h_{a}-1\\}$. In other words $[\sigma(a)]\cap
T^{k_{j}-k_{i}}[\sigma(a)]\neq\emptyset$. This again implies that word
$w=x_{-\ell}\cdots x_{0}\cdots x_{\ell}$ has two different decompositions (of
the form (4.2)), which is a contradiction. Hence for every $x\in X$ there is a
unique $a\in{\mathcal{A}}$ and $k\in\\{0,...,h_{a}-1\\}$ such that $x\in
T^{k}[\sigma(a)]$. This proves the theorem for $n=1$.

The statement for $n>1$ is proved similarly. It follows from the fact that if
$\sigma$ is a bounded length left determined substitution, then, for every
$n>1$, $\sigma^{n}$ is also a left determined substitution (Theorem 3.6), and
we can repeat the above proof for $\sigma^{n}$. Therefore, the decomposition
of $X_{\sigma}$ analogous to (4.3) holds. ∎

For completion, we state an analogue of the existence of K-R partition for
constant length substitutions (in other words, the substitution matrix has the
equal row sum property) which follows immediately from Theorem 4.1.

######  Corollary 4.2.

Let $\sigma$ be a left determined substitution of constant length $L$ on a
countably infinite alphabet ${\mathcal{A}}$, and let $(X_{\sigma},T)$ be the
corresponding subshift. Then, for every $n\in{\mathbb{N}}$,

$X_{\sigma}=\underset{a\in{\mathcal{A}}}{\bigsqcup}\,\,\,\,\underset{k=0}{\overset{L^{n}-1}{\bigsqcup}}\,T^{k}[\sigma^{n}(a)].$
(4.4)

The next theorem gives another version of K-R partitions for subshifts
associated with left determined substitutions on countably infinite alphabets.
Note that here we do not need the assumption of bounded length.

######  Theorem 4.3.

Let $\sigma$ be a left determined substitution on a countably infinite
alphabet ${\mathcal{A}}$, and let $(X_{\sigma},T)$ be the corresponding
subshift. Then, for any $n\in{\mathbb{N}}$, there exists a subset
$\mathcal{P}_{n}\subset\mathcal{L}_{n}$ of words of length $n$, such that
$X_{\sigma}$ can be partitioned into Kakutani-Rokhlin towers given by

$X_{\sigma}=\underset{a_{0}\cdots
a_{n-1}\in\mathcal{P}_{n}(\sigma)}{\bigsqcup}\,\,\,\underset{k=0}{\overset{h_{a_{0}}+...+h_{a_{n-1}}-1}{\bigsqcup}}\,T^{k}[\sigma(a_{0}\cdots
a_{n-1})]$ (4.5)

where $h_{a_{k}}=|\sigma(a_{k})|$ for $k\in\\{0,..,n-1\\}$.

###### Proof.

The proof for $n=1$ follows from (4.3). We will prove the theorem for $n=2$ in
two steps. In the first step, we show that the expression

$\underset{a_{i}a_{j}\in\mathcal{L}_{2}(\sigma)}{\bigsqcup}\,\,\underset{k=0}{\overset{h_{a_{i}}+h_{a_{j}}-1}{\bigsqcup}}\,T^{k}[\sigma(a_{i}a_{j})]$
(4.6)

contains two disjoint copies of $X_{\sigma}$ given by

$X_{\sigma}=\underset{a_{i}a_{j}\in\mathcal{L}_{2}(\sigma)}{\bigsqcup}\,\,\,\underset{k=0}{\overset{h_{a_{i}}-1}{\bigsqcup}}\,T^{k}[\sigma(a_{i}a_{j})]$
(4.7)

and

$X_{\sigma}=\underset{a_{i}a_{j}\in\mathcal{L}_{2}(\sigma)}{\bigsqcup}\,\,\,\underset{k=h_{a_{i}}}{\overset{h_{a_{i}}+h_{a_{j}}-1}{\bigsqcup}}\,T^{k}[\sigma(a_{i}a_{j})].$
(4.8)

In the second step, we provide an algorithm to remove a copy of $X_{\sigma}$
from (4.6), thus proving (4.5). The first step is similar to the proof of
Theorem 4.1. To see that (4.7) holds, let $x=\\{x_{i}\\}_{i\in{\mathbb{Z}}}\in
X_{\sigma}$ and consider the word $w=x_{-\ell}\cdots x_{0}\cdots x_{\ell}$ of
length $2\ell+1$ (here $\ell$ is the same as in the proof of Theorem 4.1).
Again, using the fact that $\sigma$ is left determined, we obtain a unique
representation of $w$ given by

$w=w_{-p}w_{-p+1}\cdots w_{0}\cdots
w_{s-1}w_{s}=w_{-p}\sigma(a_{-p+1})\cdots\sigma(a_{0})\cdots\sigma(a_{s-1})w_{s}$
(4.9)

for $a_{j}\in{\mathcal{A}}\,,\,j\in\\{-p,...,0,...,s\\}$ where $p,s$ are
positive integers. We use the labeling $\\{-p,...,0,...,s\\}$ such that
$x_{0}\in\sigma(a_{0})$. Also, by definition of left determined substitutions,
$w_{-p}$ and $w_{s}$ are either empty words or a suffix of $\sigma(a_{-p})$
and a prefix of $\sigma(a_{s})$, respectively.

Instead of considering $x_{0}\in\sigma(a_{0})$, we consider
$x_{0}\in\sigma(a_{0}a_{1})$ where $a_{0}a_{1}\in\mathcal{L}_{2}(\sigma)$.
Again as in proof of Theorem 4.1, we denote $h_{0}:=h_{a_{0}}=|\sigma(a_{0})|$
and set $\sigma(a_{0})=b_{1}\cdots b_{h_{0}}$, where $b_{i}\in{\mathcal{A}}$
for $i\in\\{1,2\cdots,h_{0}\\}$. Note that by uniqueness of the decomposition
in (4.9), the two-letter word $a_{0}a_{1}\in\mathcal{L}_{2}(\sigma)$ is
uniquely determined. Moreover, $x_{0}=b_{j}$ for some
$j\in\\{1,2...,h_{0}\\}$. Define

$y=(y_{i}),\,y_{i}=x_{i-(j-1)},\,\mathrm{for}\,\mathrm{all}\,\,i\in{\mathbb{Z}}.$

Set $j-1=k$, then $T^{-k}x=y$. Since $y\in[\sigma(a_{0}a_{1})]$, we obtain
$x\in T^{k}[\sigma(a_{0}a_{1})]$ for some $k\in\\{0,...,h_{0}-1\\}$. This
proves (4.7). Since $\sigma$ is left determined, (from an argument similar to
the proof of Theorem 4.1) it follows that the two unions in (4.7) are
disjoint.

To prove (4.8), we consider $x\in\sigma(a_{-1}a_{0})$ (instead
$x\in\sigma(a_{0}a_{1})$). Repeating the argument similar to that above, we
will show that (4.8) holds. This proves that the expression (4.6) contains two
disjoint copies of $X_{\sigma}$.

Now, we provide an algorithm allowing us to construct a K-R partition of
$X_{\sigma}$ using the towers from (4.6). Let $\\{a_{1},a_{2},a_{3},...\\}$ be
an enumeration of ${\mathcal{A}}$. Define a total order $<$ on
${\mathcal{A}}$, by $a_{i}<a_{j}$ if and only if $i<j$ for
$i,j\in{\mathbb{N}}$. The order $<$ generates the lexicographic order (denoted
by $\ll$) on elements $a_{i}a_{j}\in\mathcal{L}_{2}(\sigma)$. This is a total
order on the set $\mathcal{L}_{2}(\sigma)$. Arrange the towers in expression
(4.6) in the increasing lexicographic order of the base elements from left to
right, i.e., the tower with base $\sigma(a_{i}a_{j})$ is on the left of the
tower with the base $\sigma(a_{k}a_{\ell})$ if and only of $a_{i}a_{j}\ll
a_{k}a_{\ell}$. Let $\sigma(a_{1}a_{2})$ be the base of the first tower (or
leftmost tower, which we denote by $T_{1}$ for simplicity) in the arrangement
of towers. Let a point $x\in X_{\sigma}$ lies in
$\underset{k=a_{1}}{\overset{h_{a_{1}}+h_{a_{2}}-1}{\bigsqcup}}\,T^{k}[\sigma(a_{1}a_{2})]$,
i.e. $x$ lies in upper levels of $T_{1}$. Proceed in lexicographic order from
left to right and find the smallest tower (in the lexicographic order) to the
right of the $T_{1}$ that also contains $x$. Remove this tower from the
collection. Now repeat the process for the next (in the lexicographic order)
remaining tower in the arrangement and so forth. Let
$\mathcal{P}_{2}\subset\mathcal{L}_{2}$ denote the collection of words $w$ of
length two such that $[\sigma(w)]$ form the base of towers in the final
collection. This gives us (4.5) for $n=2$. The proof for $n>2$ follows
similarly. ∎

##  5\. Substitutions on infinite alphabet as Borel dynamical systems

Let $(X_{\sigma},T)$ be the subshift associated with a substitution $\sigma$
on a countably infinite alphabet ${\mathcal{A}}$. We recall that the space
$X_{\sigma}\subset{\mathcal{A}}^{{\mathbb{Z}}}$ is equipped with the subspace
topology $\omega$ inherited from the metric topology on
${\mathcal{A}}^{{\mathbb{Z}}}$ (see (2.1)). Then $(X_{\sigma},\omega)$ is a
$0$-dimensional Polish space. By ${\mathcal{B}}$, we denote the sigma-algebra
generated by open sets in $X_{\sigma}$ so that $(X_{\sigma},{\mathcal{B}})$ is
a standard Borel space. The left shift $T$ is a Borel automorphisms, i.e.,
$T\in Aut(X_{\sigma},{\mathcal{B}})$. In the rest of this paper, we will
consider the subshift $(X_{\sigma},T)$ as a Borel dynamical system. This
allows us to interpret subshifts from a different perspective and use some
methods of Borel dynamics. It is not hard to see that $T$ is, in fact, a
homeomorphism of $X_{\sigma}$.

###  5.1. Nested sequence of complete sections

Our goal is to construct a Bratteli-Vershik model of the subshift
$(X_{\sigma},T)$ associated with a left determined substitution $\sigma$ on a
countable alphabet (see Section 6). An important ingredient of this
construction is a nested sequence of complete sections (see Definition 2.7).
Here, we will provide two ways (Corollary 5.2 and Corollary 5.5) to construct
nested sequences of complete sections for subshifts. Since there are many
interesting examples of bounded size substitutions on countably infinite
alphabets (see Definition 2.3), we will focus on this type of substitutions in
this paper. This assumption has some direct implications: for example, it
allows us to control the cardinality of the intersection of the sequence of
complete sections (Proposition 5.1), which, in turn, helps us to control the
cardinality of the sets of minimal and maximal paths in the path space of the
corresponding Bratteli-Vershik model (see Section 6).

We recall that the notation $[\cdot]$ is used for a cylinder set of
$X_{\sigma}$.

######  Proposition 5.1.

Let $\sigma$ be a bounded size left determined substitution on a countable
alphabet ${\mathcal{A}}$. We define the sequence of Borel sets
$\\{A_{n}\\}_{{\mathbb{N}}_{0}}$ as follows:

$A_{n}=\underset{a_{i}\in{\mathcal{A}}}{\bigsqcup}[\sigma^{n}(a_{i})],\,\,\,\textrm{for}\,\,n\in{\mathbb{N}}_{0}.$
(5.1)

Then the set $\underset{n\in{\mathbb{N}}_{0}}{\bigcap}A_{n}$ is at most
countably infinite.

###### Proof.

For $x\in\underset{n\in{\mathbb{N}}_{0}}{\bigcap}A_{n}$, there exists a
sequence of letters $(a_{n})_{n\in{\mathbb{N}}}$ such that
$x\in[\sigma(a_{1})]$, $x\in[\sigma^{2}(a_{2})]$,…,
$x\in[\sigma^{n}(a_{n})]$,… and so forth. Thus, to find the cardinality of
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}A_{n}$, we need to find out how many
sets of the form $\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]$
are non-empty, and then determine the cardinality of each such set.

To determine how many sets can have the above form, pick the smallest
$k\in{\mathbb{N}}$ such that $2^{k-2}\geq N_{\sigma}$. Then
$|\sigma^{k}(a_{k})|\geq 2^{k}\geq N_{\sigma}$ and it has a unique
$\sigma$-decomposition of the form

$\sigma^{k}(a_{k})=w_{1}\sigma(b_{2})\cdots\sigma(b_{s-1})w_{s}\,;\,b_{i}\in{\mathcal{A}}\,,\,i\in\\{1,2,...,s\\},$
(5.2)

where $w_{1}$ and $w_{s}$ are either empty words or a suffix of
$\sigma(b_{1})$ and a prefix of $\sigma(b_{s})$, respectively. Since

$\sigma(\sigma^{k-1}(a_{k}))=w_{1}\sigma(b_{2})\cdots\sigma(b_{s-1})w_{s},$
(5.3)

it implies $w_{1}=\sigma(b_{1})$ and $w_{s}=\sigma(b_{s})$, i.e.

$\sigma(\sigma^{k-1}(a_{k}))=\sigma(b_{1}b_{2}\cdots b_{s})$ (5.4)

By Theorem 3.5, the map

$\sigma:\underset{n\geq
N_{\sigma}}{\bigcup}{\mathcal{L}}_{\sigma}(n)\rightarrow{\mathcal{A}}^{+}$

is injective. Note that $|\sigma^{k-1}(a_{k})|\geq 2^{k-1}\geq N_{\sigma}$,
hence relation (5.4) implies

$\sigma^{k-1}(a_{k})=b_{1}b_{2}\cdots b_{s}.$ (5.5)

Since we assumed that $2^{k-2}\geq N_{\sigma}$, Theorem 3.5 implies that the
map $\sigma^{k-1}:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is injective.
Hence, by (5.5) and the fact that the word $b_{1}\cdots
b_{s}\in{\mathcal{A}}^{+}$ is unique, we get that $a_{k}$ is unique. A similar
argument shows the uniqueness of $a_{n}$ for all $n>k$. Since $\sigma$ is of
bounded size, once we fix $a_{k}$, there are $(2t+1)$ choices for $a_{k-1}$,
$(2t+1)^{2}$ choices for $a_{k-2}$,…., and $(2t+1)^{k-1}$ choices for $a_{0}$.
Here $t\in{\mathbb{N}}$ is the size of $\sigma$ (see Definition 2.3). In other
words, for a fixed $a_{k}$, there are finitely many choices left for terms
$a_{0}$, .., $a_{k-1}$. We have proved the following result: If
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]\neq\emptyset$,
then there exist a $k\in{\mathbb{N}}$ such that for all $n\geq k$, $a_{n}$ is
uniquely determined and there are finitely many choices left for terms
$a_{0},..,a_{k-1}$. It follows from the proved result that there exist
countably many non-empty sets of the form
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]$.

To complete the proof of the proposition, we will show the following: If for a
sequence of letters $(a_{n})_{n\in{\mathbb{N}}_{0}}$ the set
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]$ is non-empty,
then it is a singleton set. For this, assume that
$x\in\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]$, and choose
$k\in{\mathbb{N}}$ such that $2^{k-1}\geq N_{\sigma}$. We consider the
cylinder set $[\sigma^{k}(a_{k})]$ containing $x$. By Theorem 3.5, the map
$\sigma^{k}:{\mathcal{A}}\rightarrow{\mathcal{A}}^{+}$ is injective, and this
means that the set $x_{[0,...,|\sigma^{k}(a_{k})|-1]}$ is uniquely defined. As
$k\rightarrow\infty$, we see that the string $\\{x_{i}\\}_{i\geq 0}$ is
uniquely defined. It remains to show that the same is true for
$\\{x_{i}\\}_{i<0}$. Consider the point $y=T^{-1}x$. Note that for every
$n\in{\mathbb{N}}$, there exists $a^{\prime}_{n}\in{\mathcal{A}}$ such that
$y\in T^{(|\sigma^{n}(a^{\prime}_{n})|-1)}[\sigma^{n}(a^{\prime}_{n})]$. In
other words, for every $n\in{\mathbb{N}}$, $y$ lies on the top of a Kakutani-
Rokhlin tower (see (4.1)), with base $[\sigma^{n}(a^{\prime}_{n})]$ for some
$a^{\prime}_{n}\in{\mathcal{A}}$. Put
$z^{(n)}:=T^{-(|\sigma^{n}(a^{\prime}_{n})|-1)}y$ for each $n\in{\mathbb{N}}$.
Pick $p\in{\mathbb{N}}$ such that $2^{p-1}\geq N_{\sigma}$, then applying the
same proof as in (5.2) through (5.5), we get that the word
$\sigma^{p}(a^{\prime}_{p})$ is uniquely determined. Hence the cylinder set
$[\sigma^{p}(a^{\prime}_{p})]$ is unique. Since
$z^{(p)}\in[\sigma^{p}(a^{\prime}_{p})]$, this fixes the entries
$z^{(p)}_{[0,...,|\sigma^{p}(a^{\prime}_{p})|-1]}$. Note that

$z^{(p)}_{[0,...,|\sigma^{p}(a^{\prime}_{p})|-1]}=y_{[-(|\sigma^{p}(a^{\prime}_{p})|-1),...,0]}=x_{[-(|\sigma^{p}(a^{\prime}_{p})|),...,-1]}.$

Thus, it proves that $x_{[-(|\sigma^{p}(a^{\prime}_{p})|),...,-1]}$ is
uniquely determined. As $p\rightarrow\infty$, the set $\\{x_{i}\\}_{i<0}$ is
uniquely determined, too. Hence, we have shown that if the set
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}[\sigma^{n}(a_{n})]$ is non-empty,
then it is a singleton set. This completes the proof of the proposition. ∎

The following corollary is an important tool in the construction of Bratteli-
Vershik models for substitutions on infinite alphabets (see Section 6).

######  Corollary 5.2.

Let $\sigma$ be a bounded size left determined substitution on countably
infinite alphabet ${\mathcal{A}}$, and let $(X_{\sigma},T)$ be the
corresponding subshift. Then the sequence of Borel sets
$(A_{n})_{n\in{\mathbb{N}}_{0}}\subset X_{\sigma}$, defined in (5.1), has
following properties:

  1. (a)

$X_{\sigma}=A_{0}\supset A_{1}\supset A_{2}\supset A_{3}...\,$;

  2. (b)

The countable set $A_{\infty}:=\underset{n\in{\mathbb{N}}_{0}}{\bigcap}A_{n}$
is a wandering set with respect to $T$;

  3. (c)

$A_{n}$ is a complete $T$-section for each $n\in{\mathbb{N}}_{0}$;

  4. (d)

For each $n\in{\mathbb{N}}_{0}$, every point in $A_{n}$ is recurrent, i.e.,
the $T$-orbit of every point returns to $A_{n}$.

###### Proof.

Note that for all $n\in{\mathbb{N}}$ and $a\in{\mathcal{A}}$, there exists
$b\in{\mathcal{A}}$ such that, $[\sigma^{n}(a)]\subset[\sigma^{n-1}(b)]$. To
see this, assume that for some $a\in{\mathcal{A}}$, there exists
$t\in{\mathbb{N}}$ such that $[\sigma^{t}(a)]\not\subset[\sigma^{t-1}(b)]$ for
every $b\in{\mathcal{A}}$. This implies that there is no letter
$b\in{\mathcal{A}}$, such that $\sigma^{t-1}(b)$ forms the first
$|\sigma^{t-1}(b)|$ entries of the word $\sigma^{t}(a)$. This, in turn,
implies that there is no letter $b\in{\mathcal{A}}$, such that $b$ is the
first letter in the word $\sigma(a)$, which is a contradiction. This
observation together with the definition of $A_{n}$ proves $(a)$.

The set $A_{\infty}$ is a countable set, see Proposition 5.1. Note that
$A_{\infty}$, $T(A_{\infty})$, $T^{2}(A_{\infty})$…,$T^{n-1}(A_{\infty})$ are
pairwise disjoint for every $n$ because of Proposition 5.1. Therefore,
$A_{\infty}$ is a wandering set. This proves part $(b)$.

To see that $(c)$ and $(d)$ are true, we remark that, for every
$n\in{\mathbb{N}}$, $A_{n}$ is the union of bases of Rokhlin towers given in
(4.1). Hence, for every $n\in{\mathbb{N}}$, $A_{n}$ is a complete section, and
every point in $A_{n}$ is recurrent. ∎

By Theorem 4.1, for $n\in{\mathbb{N}}$, $X_{\sigma}$ is decomposed into
$T$-towers

$\xi_{n}(a)=\\{T^{i}[\sigma^{n}(a)]:i=0,...,(h^{n}_{a}-1)\\},\,\,\,\,a\in{\mathcal{A}}$
(5.6)

where $h_{a}=|\sigma(a)|$. In other words, for $a\in{\mathcal{A}}$,
$\xi_{n}(a)$ denotes a tower of height $h^{n}_{a}-1$ with cylinder set
$[\sigma^{n}(a)]$ as its base. For $n\in{\mathbb{N}}$, we will denote by

$\xi_{n}=\\{\xi_{n}(a):a\in{\mathcal{A}}\\}$ (5.7)

the countable partition of $X_{\sigma}$. For sake of completion, we denote by
$\xi_{0}$ the following countable partition of $X_{\sigma}$:

$\xi_{0}=\underset{a_{i}\in{\mathcal{A}}}{\bigsqcup}[a_{i}].$

######  Remark 5.3.

Let $(\xi_{n})_{n\in{\mathbb{N}}_{0}}$ be the sequence of countable partition
defined above. Observe that,

$(i)$ $\xi_{n+1}$ refines $\xi_{n}$ for every $n\in{\mathbb{N}}_{0}$. To see
this, note that for every $n\in{\mathbb{N}}$, and $a\in{\mathcal{A}}$, there
exist $b\in{\mathcal{A}}$ such that $[\sigma^{n}(a)]\subset[\sigma^{n-1}(b)]$;

$(ii)$ $\bigcup_{n}\xi_{n}$ generates the sigma-algebra of Borel sets
${\mathcal{B}}$;

$(iii)$ all elements of partitions $\xi_{n}$, $n\in{\mathbb{N}}_{0}$ are
clopen in the topology $\omega$.

Now we provide another construction of a nested sequence of complete sections
for the subshift $(X_{\sigma},T)$ corresponding to a left determined
substitution $\sigma$ on a countably infinite alphabet ${\mathcal{A}}$. Note
that we do not need the assumption of bounded size in this construction.

######  Proposition 5.4.

Let $\sigma$ be a left determined substitution on a countable alphabet
${\mathcal{A}}$. We define a sequence of Borel sets
$\\{B_{n}\\}_{{\mathbb{N}}_{0}}$ as follows: Put $X_{\sigma}=B_{0}$ and for
$n\in{\mathbb{N}}$,

$B_{n}=\underset{a_{1}\cdots.a_{n}\in\mathcal{P}_{n}(\sigma)}{\bigsqcup}[\sigma(a_{1}\cdots.a_{n})]$
(5.8)

where $\mathcal{P}_{n}\subset\mathcal{L}_{n}$ is a set of words of length $n$
as in Theorem 4.3. Then the set
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}B_{n}$ is at most countably infinite.

###### Proof.

The proof of this proposition is similar to the proof of Proposition 5.1,
hence we only provide a sketch. The fact that the cardinality of
$\underset{n\in{\mathbb{N}}_{0}}{\bigcap}B_{n}$ is countably infinite is
proved by showing that any non-empty set of the form
$\underset{n\in{\mathbb{N}}}{\bigcap}[\sigma(a_{1}...a_{n})]$, where
$a_{1}....a_{n}\in\mathcal{L}_{n}(\sigma)$ for every $n\in{\mathbb{N}}$, is a
singleton set and that there exist countably many infinite non-empty sets of
such form. This statement follows from the fact that $\sigma$ is left
determined by applying arguments similar to that used in the proof of
Proposition 5.1. ∎

######  Corollary 5.5.

$\mathrm{(Wandering)}$ Let $\sigma$ be a left determined substitution on a
countably infinite alphabet ${\mathcal{A}}$ and $(X_{\sigma},T)$ be the
corresponding subshift. Then the sequence of Borel sets
$(B_{n})_{n\in{\mathbb{N}}_{0}}\subset X_{\sigma}$, defined in (5.8), has
following properties,

  1. (a)

$X_{\sigma}=B_{0}\supset B_{1}\supset B_{2}\supset B_{3}...\,\,\,.$

  2. (b)

The cardinality of $B_{\infty}:=\underset{n\in{\mathbb{N}}_{0}}{\bigcap}B_{n}$
is countably infinite and it is a wandering set.

  3. (c)

$B_{n}$ is a complete $T$-section for each $n\in{\mathbb{N}}_{0}$.

  4. (d)

For each $n\in{\mathbb{N}}_{0}$ every point in $B_{n}$ is recurrent.

###### Proof.

The proof is similar to Corollary 5.2, hence we omit it. ∎

##  6\. Generalized Bratteli-Vershik models for infinite substitutions.

###  6.1. Generalized Bratteli diagrams

The notion of a generalized Bratteli diagram is a natural extension of the
notion of a Bratteli diagram, where each level in the diagram is allowed to be
countable. It was proved in [BDK06] that any aperiodic Borel automorphism can
be realized as a Vershik map on the path space of a generalized Bratteli
diagram, see Theorem 6.10 below. In this section, we will provide an algorithm
to construct a generalized stationary Bratteli-Vershik model for a subshift
associated with a bounded size left determined substitution on a countably
infinite alphabet.

######  Definition 6.1.

A generalized Bratteli diagram is a graded graph $B=(V,E)$ such that the
vertex set $V$ and the edge set $E$ can be represented as partitions
$V=\bigsqcup_{i=0}^{\infty}V_{i}$ and $E=\bigsqcup_{i=0}^{\infty}E_{i}$
satisfying the following properties:

$(i)$ The number of vertices at each level $V_{i}$, $i\in{\mathbb{N}}_{0}$, is
countably infinite (in most cases, we will identify each $V_{i}$ with either
${\mathbb{Z}}$ or ${\mathbb{N}}$). For all $i\in{\mathbb{N}}_{0}$, $E_{i}$
represents the countable set of edges between the levels $V_{i}$ and
$V_{i+1}$.

$(ii)$ The range and source maps $r,s:E\rightarrow V$ are defined on the
diagram $B$ such that $r(E_{i})\subset V_{i+1}$ and $s(E_{i})\subset V_{i}$
for each $i\in{\mathbb{N}}_{0}$. Moreover, for all $v\in V$,
$s^{-1}(v)\neq\emptyset$, and, for all $v\in V\setminus V_{0}$,
$r^{-1}(v)\neq\emptyset$.

$(iii)$ For every vertex $v\in V\setminus V_{0}$, $|r^{-1}(v)|<\infty$.

For a vertex $v\in V_{i}$ and a vertex $w\in V_{i+1}$, we will denote by
$E(v,w)$ the set of edges between $v$ and $w$. It follows from Definition 6.1
that the set $E(v,w)$ is either finite or empty for every fixed pair of
vertices $(v,w)$. Set $f^{(i)}_{w,v}=|E(v,w)|$ for every $v\in V_{i}$ and
$w\in V_{i+1}$. In such a way, we associate with a generalized Bratteli
diagram $B=(V,E)$ a sequence of non-negative infinite matrices $F_{i}$
($i\in{\mathbb{N}}_{0}$) that are called the incidence matrices and given by

$F_{i}=(f^{(i)}_{w,v}:w\in V_{i+1},v\in V_{i}),\ \
f^{(i)}_{w,v}\in{\mathbb{N}}_{0}.$

######  Remark 6.2.

The next observations follow directly from Definition 6.1:

$(1)$ The structure of a generalized Bratteli diagram is completely determined
by the sequence of incidence matrices $(F_{n}),\,n\in{\mathbb{N}}_{0}$. We
will write $B=B(F_{n})$ to emphasize that the generalized Bratteli diagram $B$
is determined by $(F_{n})$.

$(2)$ For each $n\in{\mathbb{N}}_{0}$, the matrix $F_{n}$ has at most finitely
many non-zero entries in each row and none of its rows or columns are entirely
zero. A column of $F_{n}$ can have a finite or infinite number of non-zero
entries.

$(3)$ If for every $n\in{\mathbb{N}}_{0}$ the matrix $F_{n}$ is same,
$F_{n}=F$, then we call the generalized Bratteli diagram stationary. We will
write $B=B(F)$ in this case.

Figure 1 is an example of a generalized Bratteli diagram. Clearly, we can see
only a finite part of the diagram as there are countably many levels and each
level has countably many vertices.

Figure 1. Example of a Bratteli diagram: levels, vertices, and edges (see
Definition 6.1)

If the level $V_{0}$ consists of a single vertex and each set $V_{n}$ is
finite, then we get the usual definition of a Bratteli diagram which was first
defined in [Bra72] and used to model Cantor dynamical systems and classify
them with respect to orbit equivalence (see [HPS92], [GPS95]).

######  Definition 6.3.

A finite or infinite path in a generalized Bratteli diagram $B=(V,E)$ is a
sequence of edges $(e_{i},\,i\in{\mathbb{N}}_{0})$ such that
$r(e_{i})=s(e_{i+1})$ for each $i$. For a diagram $B=(V,E)$, we will denote by
$Y_{B}$ the set of all infinite paths in $B$. This set is called the path
space of the generalized Bratteli diagram $B=(V,E)$. If
$\overline{e}=(e_{0},...,e_{n})$ is a finite path in $B=(V,E)$, then the set

$[\overline{e}]:=\\{x=(x_{i})\in Y_{B}:x_{0}=e_{0},...,x_{n}=e_{n}\\},$ (6.1)

is called the cylinder set associated with $\overline{e}$. It is the set
containing all infinite paths with the first $n+1$ entries same as in
$\overline{e}$.

Two paths $x=(x_{i})$ and $y=(y_{i})$ are called tail invariant if there
exists some $n$ such that $x_{i}=y_{i}$ for all $i>n$. This notion defines a
countable Borel equivalence relation $\mathcal{R}$ on the path space $Y_{B}$
which is called the tail equivalence relation.

For $v\in V_{0}$ and $w\in V_{n}$, $n\in{\mathbb{N}}$, we will denote the
finite path starting at $v$ and ending at $w$ by $\overline{e}(v,w)$ and the
corresponding cylinder set by $[\overline{e}(v,w)]$.

######  Remark 6.4.

In this remark, we collect several obvious statements about the path space
$Y_{B}$ of a generalized Bratteli diagram $B$.

$(1)$ The path space $Y_{B}$ is a zero-dimensional Polish space with the
topology generated by cylinder sets. Moreover, every cylinder set is a clopen
set in this topology. This topology coincides with the topology generated by
the following metric on $Y_{B}$: for $x=(x_{i}),\,y=(y_{i})$, define

$\mathrm{dist}(x,y)=\frac{1}{2^{N}},\ \ \
N=\min\\{i\in{\mathbb{N}}_{0}:x_{i}\neq y_{i}\\}.$

$(2)$ The path space $Y_{B}$ of a generalized Bratteli diagram is a standard
Borel space, where the Borel structure is generated by clopen (cylinder) sets.
In general, $Y_{B}$ is not locally compact. One can see that $Y_{B}$ is
locally compact if every column of $F_{n}$ has finitely many non-zero entries.

$(3)$ We will assume that the path space $Y_{B}$ of a generalized Bratteli
diagrams $B$ has no isolated points, i.e., for every infinite path
$(x_{0},x_{1},x_{2},...)\in Y_{B}$ and every $n\in{\mathbb{N}}_{0}$, there
exists a level $m>n$ such that $|s^{-1}(r(x_{m}))|>1$.

######  Definition 6.5.

Given a generalized Bratteli diagram $B=(V,E)$ and a monotone increasing
sequence $(n_{k}:k\in{\mathbb{N}}_{0}),n_{0}=0$, we define a new generalized
Bratteli diagram $B^{\prime}=(V^{\prime},E^{\prime})$ as follows: the vertex
sets are determined by $V^{\prime}_{k}=V_{n_{k}}$, and the edge sets
$E^{\prime}_{k}=E_{n_{k+1}-1}\circ...\circ E_{n_{k}}$ are formed by finite
paths between the levels $V^{\prime}_{k}$ and $V^{\prime}_{k+1}$. The diagram
$B^{\prime}=(V^{\prime},E^{\prime})$ is called a telescoping of the original
diagram $B=(V,E)$. The incidence matrices of $B^{\prime}$ are the products of
incidence matrices of $B$: $F^{\prime}_{k}=F_{n_{k+1}-1}\circ...\circ
F_{n_{k}}$.

For a generalized Bratteli diagram $B=(V,E)$, we define a partial order $\geq$
on each edge set $E_{i}$ as follows: for every $v\in V_{i+1}$, equip the
finite set $r^{-1}(v)$ with a linear order $\geq$ so that any two edges
$e,e^{\prime}\in E_{i}$ are comparable if and only if they have the same
range, $r(e)=r(e^{\prime})$. Since we do this for each
$E_{i}\,(i\in{\mathbb{N}}_{0})$, we obtain a partial order $\geq$ on the set
of finite paths. Using the partial order $\geq$, we can define a partial
lexicographic order on the set of all paths between any two levels (say
$V_{t}$ and $V_{s}$ for $s>t$): $(e_{t},...,e_{s-1})>(f_{t},...,f_{s-1})$ if
and only if for some $i$ with $t\leq i<s$, $e_{j}=f_{j}$ for $i<j<s$ and
$e_{i}>f_{i}$.

Applying this lexicographic order, we can compare any two finite paths in
$E(V_{0},w)$, the set of all finite paths from level $V_{0}$ to a vertex $w\in
V_{n}$ for some $n>0$. This means that every set $E(V_{0},w)$ contains one
maximal path and one minimal path. For an infinite path
$e=(e_{0},e_{1},...,e_{i},...)$, we say that it is maximal if $e_{i}$ is
maximal in the set $r^{-1}(r(e_{i}))$ for each $i\in{\mathbb{N}}_{0}$.
Similarly, we can define a minimal path. We will denote by $Y_{max}$
(respectively $Y_{min}$) the set of maximal (respectively minimal) infinite
paths in $Y_{B}$. Clearly, $Y_{max}$ and $Y_{min}$ are Borel sets.

######  Definition 6.6.

A generalized Bratteli diagram $B=(V,E)$ together with a partial order $\geq$
on $E$ is called a generalized ordered Bratteli diagram and denoted by
$B=(V,E,\geq)$. A generalized stationary Bratteli diagram is called stationary
ordered if the linear order on $r^{-1}(v)$ is the same for all vertices $v$
independent of the level.

######  Definition 6.7.

For a generalized ordered Bratteli diagram, we define a Borel transformation

$\varphi:Y_{B}\setminus Y_{max}\rightarrow Y_{B}\setminus Y_{min}$

as follows: given $x=(x_{0},x_{1},...)\in Y_{B}\setminus Y_{max}$, let $m$ be
the smallest number such that $x_{m}$ is not maximal. Let $g_{m}$ be the
successor of $x_{m}$ in the set $r^{-1}(r(x_{m}))$. Then we define
$\varphi(x)=(g_{0},g_{1},...,g_{m-1},g_{m},x_{m+1},...)$ where
$(g_{0},g_{1},...,g_{m-1})$ is the minimal path in $E(V_{0},r(g_{m-1}))$. It
is not difficult to check that the map $\varphi$ is a Borel bijection. If we
can extend $\varphi$ bijectively to the entire path space $Y_{B}$, then we
call the Borel transformation $\varphi:Y_{B}\rightarrow Y_{B}$ a Vershik map,
and the Borel dynamical system $(Y_{B},\varphi)$ is called a generalized
Bratteli-Vershik system.

######  Remark 6.8.

The Vershik map $\varphi$ admits a Borel extension to $Y_{B}$ if and only if
$|Y_{max}|=|Y_{min}|$. This relation includes the cases when the sets
$Y_{max}$ and $Y_{min}$ are finite, countable, and uncountable.

######  Lemma 6.9.

Let $\mu$ be a finite or sigma-finite measure on the path space $Y_{B}$ of a
generalized ordered Bratteli diagram, and $\varphi$ the Vershik map. If
$\mu(Y_{max})=\mu(Y_{min})=0$, then $\mu$ is tail invariant if and only if
$\mu$ is $\varphi$-invariant.

The following result shows that for any aperiodic Borel automorphism of a
standard Borel space there exists a generalized Bratteli-Vershik model.

######  Theorem 6.10 ([BDK06]).

Let $T$ be an aperiodic Borel automorphism acting on a standard Borel space
$(X,{\mathcal{B}})$. Then there exists a generalized ordered Bratteli diagram
$B=(V,E,\geq)$ and a Vershik automorphism $\varphi:X_{B}\to X_{B}$ such that
$(X,T)$ is Borel isomorphic to $(X_{B},\varphi)$.

######  Example 6.11.

Substitution read on a stationary Bratteli diagram: Let $B=(V,E,\geq)$ be a
generalized stationary ordered Bratteli diagram, and let ${\mathcal{A}}$ be a
countably infinite alphabet. For each $n\in{\mathbb{N}}_{0}$, we label the set
of vertices $V_{n}$ by letters in ${\mathcal{A}}$. We denote by $v(a,n)$ the
vertex corresponding to letter $a\in{\mathcal{A}}$ on level $n$. Thus, for all
$n\in{\mathbb{N}}_{0}$, we can write $V_{n}=\\{v(a,n);a\in{\mathcal{A}}\\}$.
For a fixed $n>0$ and $a\in V_{n}$, we consider the finite set
$r^{-1}(v(a,n))$, i.e., the set of all edges with range $v(a,n)$. This is an
ordered finite set. We use the order to write

$r^{-1}(v(a,n))=(e_{1},e_{2},...,e_{m})$

where $e_{1}<e_{2}<...<e_{m}$. Note that $B$ is a stationary diagram, hence
the above set is independent of $n$. Let $a_{i}\in{\mathcal{A}}$ be such that
$s(e_{i})$ is labeled by $a_{i}$ for $i\in\\{1,2,...,m\\}$. It defines the
ordered set $(a_{1},a_{2},...,a_{m})$ of these labels. This ordered set may
contain possible repetitions. Then the map $a\mapsto a_{1}a_{2}\cdots a_{m}$
from ${\mathcal{A}}$ to ${\mathcal{A}}^{+}$ defines a substitution on
${\mathcal{A}}$ which is called the substitution read on a stationary ordered
generalized Bratteli diagram $B=(V,E,\geq)$.

######  Remark 6.12.

We provide here an alternative description for infinite paths in a generalized
Bratteli diagram $B=(V,E,\geq)$ which will be used below. We set $h(0,v)=1$
for all $v\in V_{0}$, and for $v\in V_{1}$, define $h(1,v)=|r^{-1}(v)|$. For
$v\in V_{n}$, $n>1$, we define by induction

$h(n,v)=\underset{w\in s(r^{-1}(v))}{\sum}|E(w,v)|h(n-1,w).$ (6.2)

Let $v\in V_{n}$. All finite paths in the set $E(V_{0},v)$ are comparable
under the lexicographical order described above. This allows us to enumerate
the elements of $E(V_{0},v)$ from $0$ to $h(n,v)-1$. In this enumeration, we
allot $0$ to the minimal path and $h(n,v)-1$ to the maximal path.

Let $y=(e_{0},e_{1}...)$ be an infinite path in $Y_{B}$. Consider a sequence
$(Q_{n})_{n\in{\mathbb{N}}}$ of growing finite paths defined by $y$,

$Q_{n}=(e_{0},...,e_{n-1})\in E(V_{0},r(e_{n-1})).$

This allows us to identify every $Q_{n}$ with a pair $(i_{n},v_{n})$ where
$v_{n}=r(e_{n-1})$ and $i_{n}\in[0,h(n,v_{n})-1]$ is the order given to
$Q_{n}$ in the set $E(V_{0},v_{n})$. Thus, for every $y=(e_{0},e_{1}...)\in
Y_{B}$, we can obtain a unique identifier in the form of an infinite sequence
$(i_{n},v_{n})$ where $v_{n}=r(e_{n-1})$ and $i_{n}\in[0,h(n,v_{n})-1]$,
$n\in{\mathbb{N}}$.

###  6.2. Stationary generalized Bratteli-Vershik model for substitutions on
infinite alphabet

In this section, we provide an algorithm to construct a generalized stationary
Bratteli-Vershik model for a bounded size left determined substitution
$\sigma$ on a countably infinite alphabet ${\mathcal{A}}$. Let
$(X_{\sigma},T)$ be the subshift associated with $\sigma$. We use Corollary
5.2 to obtain a nested sequence of complete sections for $(X_{\sigma},T)$

$X_{\sigma}=A_{0}\supset A_{1}\supset A_{2}\supset A_{3}....\,\,\,.$

Here the sets $A_{n}$ are defined as follows:

$A_{n}=\bigsqcup_{a\in{\mathcal{A}}}[\sigma^{n}(a)],\quad n\geq 0.$

For $n\in{\mathbb{N}}$, using (5.7), we obtain the partition $\xi_{n}$ of
$X_{\sigma}$:

$\xi_{n}=\underset{a\in{\mathcal{A}}}{\bigsqcup}\xi_{n}(a),$ (6.3)

where

$\xi_{n}(a)=\\{T^{i}[\sigma^{n}(a)]:i=0,...,(h^{n}_{a}-1)\\},\,\,\,\,a\in{\mathcal{A}}\,,\,\,\,h_{a}=|\sigma(a)|.$
(6.4)

We also define

$\xi_{0}=\underset{a\in{\mathcal{A}}}{\bigsqcup}[a].$

Set $V_{0}:=\\{[a]\\}_{a\in{\mathcal{A}}}$. Each element in the set $V_{0}$
corresponds to a vertex at level $0$ of the generalized Bratteli diagram. We
denote by $v_{a,0}$ the vertex in $V_{0}$ corresponding to the cylinder set
$[a],a\in{\mathcal{A}}$. Similarly, we denote by

$V_{1}:=\\{[\sigma(a)]\\}_{a\in{\mathcal{A}}}.$

The set $V_{1}$ is identified with cylinder sets of the form $[\sigma(a)]$ for
$a\in{\mathcal{A}}$. The set $[\sigma(a)]$ corresponds to a vertex $v_{a,1}\in
V_{1}$. Note that $[\sigma(a)]$ is the base of the tower $\xi_{1}(a)$. Then
relation (6.4) (for $n=1$) is represented as

$\xi_{1}(v_{a,1}):=\xi_{1}(a)=\\{T^{i}[\sigma(a)]:i=0,...,(h_{a}-1)\\},\,\,\,\,v_{a,1}\in
V_{1},$

and then (6.3) (for $n=1$) as

$\xi_{1}=\underset{v\in V_{1}}{\bigsqcup}\xi_{1}(v).$

We apply this construction for every $A_{n}$ in the sequence above to obtain
the corresponding partition $\xi_{n}$ of towers $\xi_{n}(v)$ of height
$h^{n}_{v}-1$. Note that Remark 5.3 implies that each $\xi_{n+1}$ refines
$\xi_{n}$ and $\bigcup_{n\in{\mathbb{N}}}\xi_{n}$ generates the
$\sigma$-algebra ${\mathcal{B}}$ of Borel sets in $X_{\sigma}$. With the help
of sequence of partitions $(\xi_{n})_{n\in{\mathbb{N}}_{0}}$ we can start
constructing the generalized Bratteli diagram $B=(V,E)$.

Recall, we denoted by $v_{b,0}$ a vertex in $V_{0}$ corresponding to cylinder
set $[b]$ for $b\in{\mathcal{A}}$. To define $E_{1}$, we take $v_{a,1}\in
V_{1}$ and corresponding cylinder set $[\sigma(a)]$. Here we are working with
a nested sequence of K-R towers. Thus every cylinder set of the form
$[\sigma(a)]$ lies in a cylinder set of the form $[b_{1}]$ for some
$b_{1}\in{\mathcal{A}}$.

Since the cylinder set $[\sigma(a)]$ is base of a tower $(\xi_{1}(a))$ of
height $h_{a,1}-1$, each level of this tower lies in a cylinder set of the
form $[b_{i}]$ for some $b_{i}\in{\mathcal{A}}$ (which were used to construct
the vertex of the $0$th level). Let $\\{[b_{1}],[b_{2}]...,[b_{h_{a}}]\\}$, be
the list of these cylinder sets from bottom to top. We connect $v_{a,1}\in
V_{1}$ to vertices $v_{b_{k},0}$ in $V_{0}$, for $k\in\\{1,..,h_{a}\\}$ with
an edge. We do this for each $v\in V_{1}$, to define $E_{1}$. To introduce a
linear order on $r^{-1}v$ for $v\in V_{1}$, we enumerate them from $1$ to
$h_{v}$ in the order they appear in the tower going bottom to top.

We repeat this procedure for every $n\in{\mathbb{N}}_{0}$ to obtain the
corresponding $V_{n}$ and partially ordered $E_{n}$. This gives us an ordered
generalized Bratteli diagram $B(V,E,\geq)$, with
$V=\bigsqcup_{i\in{\mathbb{N}}_{0}}V_{i}$ and
$E=\bigsqcup_{i\in{\mathbb{N}}_{0}}E_{i}$. It is easy to check that this
diagram satisfies the Definition 6.1. The fact that
$\big{|}\underset{n\in{\mathbb{N}}_{0}}{\bigcap}A_{n}\big{|}=\aleph_{0}$
implies that the maximal and minimal paths in $B$ are countably infinite. Note
that every infinite path $y\in Y_{B}$ is completely determined by the infinite
sequence ${(i_{n},v_{n})}_{n}$, $v_{n}\in V_{n}$, $0\leq i_{n}\leq
h(n,v_{n})-1$ such that $T^{i_{n+1}}([\sigma^{n+1}(a_{n+1})])\subset
T^{i_{n}}([\sigma^{n}(a_{n})])$, for every $n\in{\mathbb{N}}_{0}$, where the
cylinder set $[\sigma^{n}(a_{n})]$ corresponds to $v_{n}\in V_{n}$ and so on.

We claim that the generalized Bratteli diagram $B=(V,E,\geq)$ constructed
above is a stationary diagram and $\sigma$ is in fact the substitution read on
$B=(V,E,\geq)$. To see this fix $n\in{\mathbb{N}}$ and consider the vertex
sets $V_{n-1}$ and $V_{n}$ at level $(n-1)$ and $n$ respectively. In the
construction above, the partition $\xi_{n}$ is used to obtain the edge set
$E_{n}$. Recall that we identified vertices at level $n$ with sets of the form
$[\sigma^{n}(a)]$ for $a\in{\mathcal{A}}$. These sets are in fact the base of
the tower $\xi_{n}(a)$ (see (6.3)). For a vertex $v\in V_{n}$, and write
$v=V(a_{v},n)$ (see Remark 6.11) to illustrate that $v$ is a vertex on level
$n$ corresponding to letter $a_{v}\in{\mathcal{A}}$.

There exists $a_{1}\in{\mathcal{A}}$ such that we have the following
inclusion, $[\sigma^{n}(a_{v})]\subset[\sigma^{n-1}(a_{1})]$. Here
$[\sigma^{n-1}(a_{1})]$ is the base of the tower $\xi_{n-1}(a_{1})$ in
partition $\xi_{n-1}$. Now we consider the set of edges with range $v$; i.e.
the set $r^{-1}(v)$. By the above construction, this set is fully ordered. We
list its elements in increasing order $(e_{1},...,e_{s})$. For
$i\in\\{1,..,s\\}$, let $a_{i}$ be the label of the vertex (see Remark 6.11)
on level $V_{n-1}$ which is the source of edge $e_{i}$. We make an ordered
list of these labels $(a_{1},..,a_{s})$ (i.e. same order as $e_{i}$’s).

By the above construction this means that as we move from bottom to top in the
$T$-tower $\xi_{n}(a_{v})$ (with base $[\sigma^{n}(a_{v})]$) it intersects
with $T$-towers $\\{\xi_{1}(a_{1}),...,\xi_{i}(a_{s})\\}$ in the given order
(i.e. $1$ to $s$). This in turn implies

$\sigma^{n}(a_{v})=\sigma^{n-1}a_{1}....\sigma^{n-1}a_{s}.$

Hence we get $\sigma(a_{v})=a_{1}....a_{s}$. Note that we will get the same
expression for $\sigma(a_{v})$ using any level $n\in{\mathbb{N}}$, hence the
diagram $B=(V,E,\geq)$ is stationary. Moreover, the substitution we recovered
above (from the diagram) matches the substitution $\sigma$. This implies that
$\sigma$ is in-fact the substitution read on $B=(V,E,\geq)$.

The next theorem shows that the subshift $(X_{\sigma},T)$ corresponding to a
bounded size left determined substitution $\sigma$ on an infinite alphabet can
be realized as a Vershik transformation acting on the path space of an ordered
stationary generalized Bratteli diagram.

######  Theorem 6.13.

Let $\sigma$ be a bounded size left determined substitution on a countably
infinite alphabet and $(X_{\sigma},T)$ be the corresponding subshift. Then
there exists a stationary ordered Borel–Bratteli diagram $B=(V,E,\geq)$ and a
Vershik map $\varphi:Y_{B}\rightarrow Y_{B}$ such that $(X_{\sigma},T)$ is
isomorphic to $(Y_{B},\varphi)$.

Proof. We use Corollary 5.2, to obtain a nested sequence of complete sections
$(A_{n})_{n\in{\mathbb{N}}_{0}}$ corresponding to $(X_{\sigma},T)$. As
described above for $n\in{\mathbb{N}}_{0}$, let

$\xi_{n}=\xi_{n}(v),v\in V_{n}$

be the partition of $X_{\sigma}$ corresponding to
$A_{n}=\underset{a\in{\mathcal{A}}}{\bigsqcup}[\sigma^{n}(a)]$. As before by
identifying $V_{n}\ni v_{a,n}\sim[\sigma^{n}(a)]$. For convenience, we write
$A_{n}(v):=[\sigma^{n}(a)]$. Thus in general for $v\in V_{n}$,
$n\in{\mathbb{N}}_{0}$, we write

$\xi_{n}(v)=\\{T^{j}A_{n}(v):j=0,...,h(n,v)-1\\}.$

Here $h(n,v)=h^{n}(a)$ (and $[\sigma^{n}(a)]$ is the set corresponding to
$v\in V_{n}$). Remark 5.3, implies that atoms of
$(\xi_{n},n\in{\mathbb{N}}_{0})$ generate the Borel structure of $X_{\sigma}$
and are clopen. In other words, sets of the form $T^{j}(A_{n}(v)),\,\,v\in
V_{n},\,j=0,...,h(n,v)-1,n\in{\mathbb{N}}_{0}$, generate the Borel structure
of $X_{\sigma}$.

For a fixed $n\in{\mathbb{N}}_{0}$ and $\epsilon>0$, we can cut each tower
$\xi_{n}(v)$ into disjoint clopen towers of the same height with the diameter
of each new tower less than $\epsilon$. Thus we can assume,

$\underset{0\leq j<h(n,v),v\in
V_{n}}{\textrm{sup}}\,\,[\textrm{diam}\,T^{j}(A_{n}(v))]\rightarrow
0,\,\,n\rightarrow\infty.$ (6.5)

Here we use the metric defined in (2.1).

We apply the construction discussed above to the sets $(A_{n})$ and $T$ to
obtain a stationary ordered generalized Bratteli diagram $B=(V,E,\geq)$. We
define a map $\varphi$ (Vershik map) on the path space $Y_{B}$ as follows: On
$Y_{B}\setminus Y_{max}$, the $\varphi$ is defined using the algorithm in
Definition 6.7. Thus $\varphi$ is a homeomorphism from $Y_{B}\setminus
Y_{max}$ to $Y_{B}\setminus Y_{min}$. By construction, the cardinality of
$Y_{max}$ is equal to the cardinality of $Y_{min}$ (both are countably
infinite). Hence we extend $\varphi$ to entire $Y_{B}$ by defining a bijective
Borel transformation mapping the set of maximal paths to the set of minimal
paths; i.e. $\varphi(Y_{max})=Y_{min}$. To do so, consider a maximal path
$y\in Y_{max}$. Note that $y$ determines a unique sequence
${(i_{n},v_{n})}_{n}$, where $v_{n}\in V_{n}$ and $i_{n}=h(n,v_{n})-1$ (since
$y$ is a maximal path) for every $n\in{\mathbb{N}}_{0}$. More over
$T^{i_{n+1}}(A_{n+1}(v_{n+1}))\subset T^{i_{n}}(A_{n}(v_{n})),$ for every
$n\in{\mathbb{N}}_{0}$. Thus $y\in Y_{max}$ corresponds to a unique point
$x\in X_{\sigma}$ where
$\\{x\\}=\underset{n}{\bigcap}\,T^{i_{n}}A_{n}(v_{n})$. Uniqueness of $x$
follows from (6.5).

Let $\tilde{x}=T(x)$; since $T$ takes points at the top of a KR tower to
points at the bottom of the tower, $\tilde{x}$ lies in the intersections of
the base of the nested sequence of Kakutani-Rokhlin towers. Again $\tilde{x}$
determines a unique sequence ${(i_{n},v_{n})}_{n}$, where $v_{n}\in V_{n}$ and
$i_{n}=0$ (since $x$ lies in bottom of the towers) for every
$n\in{\mathbb{N}}_{0}$ and
$\\{\tilde{x}\\}=\underset{n}{\bigcap}\,A_{n}(v_{n})$. Let $\tilde{y}$ be the
unique infinite path in $Y_{B}$ corresponding to $\tilde{x}$ then by
construction $\tilde{y}\in Y_{min}$. We define $\varphi(y)=\tilde{y}$. This
gives a bijective Borel transformation mapping $Y_{max}$ to $Y_{min}$. The
bijection follows from the bijection of $T$. This together with the definition
of $\varphi:Y_{B}\setminus Y_{max}\rightarrow Y_{B}\setminus Y_{min}$ (see
Definition 6.7) gives us a Borel automorphism $\varphi:Y_{B}\rightarrow Y_{B}$
which we call the Vershik map.

Now we show that $(X_{\sigma},T)$ is Borel isomorphic to $(Y_{B},\varphi)$. To
do this we define a map $f:X_{\sigma}\rightarrow Y_{B}$ as follows: For $x\in
X_{\sigma}$, choose the unique sequence ${(i_{n},v_{n})}_{n}$, $0\leq
i_{n}\leq h(n,v_{n})-1$, $v_{n}\in V_{n}$, such that

$T^{i_{n+1}}(A_{n+1}(v_{n+1}))\subset T^{i_{n}}(A_{n}(v_{n})),$ (6.6)

for every $n\in{\mathbb{N}}_{0}$ and
$\\{x\\}=\underset{n}{\bigcap}\,T^{i_{n}}A_{n}(v_{n})$. As mentioned in Remark
6.12, such a sequence defines a unique infinite path $y\in Y_{B}$. We set
$f(x)=y$. Observe that $f$ is a continuous injective map. From the
construction of $B=(V,E,\geq)$ and definition of Vershik transformation
$\varphi$, acting on $Y_{B}$, we get that $f(Tx)=\varphi(fx)$, $x\in
X_{\sigma}$. We claim that $f$ is surjective. To see this, let $y\in Y_{B}$ be
an infinite path. Then $y$ defines an infinite sequence ${(i_{n},v_{n})}_{n}$,
$0\leq i_{n}\leq h(n,v_{n})-1$, $v_{n}\in V_{n}$, (see Remark 6.12). Thus by
(6.5) and (6.6), we obtain a single point $x$ such that $f(x)=y$. $\square$

###  6.3. Non-stationary generalized Bratteli-Vershik model for substitutions
on infinite alphabet

In Section 5 we provided two versions of nested sequence of complete sections
for a subshift associated with substitution on countably infinite alphabet
(see Corollary 5.2 and Corollary 5.5). We used Corollary 5.2, in Subsection
6.2 to construct a stationary generalized Bratteli-Vershik model for a bounded
size left determined substitution $\sigma$ on a countably infinite alphabet.

If we repeat the construction in Subsection 6.2 using Corollary 5.5 (instead
of Corollary 5.2), we will obtain alternative generalized Bratteli-Vershik
models for a left determined substitution on a countably infinite alphabet.
Since the complete sections in Corollary 5.5 are not powers of $\sigma$, an
ordered generalized Bratteli diagram constructed this way will not be
stationary in general. Nevertheless, by the same reasoning as in the proof of
Theorem 6.13, the dynamical system on the path space of this ordered (not
necessarily stationary) generalized Bratteli diagram will still be isomorphic
to $(X_{\sigma},T)$. We want to emphasize that in Corollary 5.5 (unlike
Corollary 5.2) there is no requirement for the substitution to be of bounded
size. Hence this construction will allow us to build Bratteli-Vershik models
for any left determined substitution. We obtain the following theorem :

######  Theorem 6.14.

Let $\sigma$ be a left determined substitution on a countably infinite
alphabet and $(X_{\sigma},T)$ be the corresponding subshift. Then there exists
an ordered (not necessarily stationary) generalized Bratteli diagram
$B=(V,E,\geq)$ and a Vershik map $\varphi:Y_{B}\rightarrow Y_{B}$ such that
$(X_{\sigma},T)$ is isomorphic to $(Y_{B},\varphi)$.

##  7\. Invariant measure for infinite substitution via Bratteli diagrams

For a stationary generalized Bratteli diagram with an irreducible, aperiodic,
and recurrent countable incidence matrix (see Definition 7.1), there exists a
direct method for finding a tail invariant measure on the path space of the
diagram. In the previous section, we constructed an isomorphism between the
subshift (associated with bounded size left determined substitution on a
countably infinite alphabet) and Vershik map on path space of the
corresponding stationary generalized Bratteli diagram. Therefore this method
will also provide a formula for a shift-invariant measure when the subshift is
associated with a bounded size left determined substitution on countably
infinite alphabets.

###  7.1. Tail invariant measure for stationary Bratteli diagrams

Recall that a generalized Bratteli diagram $B=B(F_{n})$ is called stationary
if, for every $n\in{\mathbb{N}}_{0}$, the incidence matrices $F_{n}=F$. Thus,
the structure of the diagram remains stationary, and the set of edges $E_{n}$
between $V_{n}$ and $V_{n+1}$ is independent of $n\in{\mathbb{N}}_{0}$. In the
rest of the paper, we will identify the set of vertices $V_{n}$ with the
integers ${\mathbb{Z}}$ for all $n$.

We discuss below some definitions and results from the theory of non-negative
infinite matrices. We refer the reader to Chapter $7$ of [Kit98] for a
detailed discussion of the Perron-Frobenius theory of such matrices.

######  Definition 7.1.

$(a)$ We call a matrix $F=(f_{ij})$ infinite if its rows and columns are
indexed by the same countably infinite set. Assuming that all matrices $F^{n}$
are defined (i.e., they have finite entries), we denote the entries of $F^{n}$
by $f^{(n)}_{ij}>0$.

$(b)$ An infinite non-negative matrix $F=(f_{ij})$, $i,j\in{\mathbb{Z}}$, is
called irreducible if, for all $i,j\in{\mathbb{Z}}$, there exists some
$n\in{\mathbb{N}}_{0}$ such that $f^{(n)}_{ij}>0$. A stationary Bratteli
diagram $B=B(F)$ is called an irreducible diagram if its incidence matrix $F$
is irreducible.

$(c)$ An irreducible matrix $F$ is said to have period $p$ if, for all
vertices $i\in{\mathbb{Z}}$,

$p=\gcd\\{t:f^{(t)}_{ii}>0\\}.$

An irreducible matrix $F$ is called aperiodic if $p=1$.

$(d)$ For an irreducible, aperiodic, non-negative, infinite matrix $F$ the
limit defined by

$\lambda=\lim_{n\to\infty}(f^{(n)}_{ii})^{\frac{1}{n}}$

exists and is independent of the choice of $i$. The value of the limit
$\lambda$ is called the Perron-Frobenius eigenvalue of $F$. We will consider
only the case of finite Perron-Frobenius eigenvalue $\lambda$.

$(e)$ It is said that an irreducible, aperiodic, non-negative, infinite matrix
$F$ is transient if

$\sum_{n\geq 1}f^{(n)}_{ij}\lambda^{-n}<\infty.$

$(f)$ It is said that an irreducible, aperiodic, non-negative, infinite matrix
$F$ is recurrent if

$\sum_{n\geq 1}f^{(n)}_{ij}\lambda^{-n}=\infty.$

$(g)$ For an irreducible, aperiodic, recurrent, non-negative, infinite matrix
$F$, let $t_{ij}(1)=f_{ij}$, and for $n>1$,

$t_{ij}(n+1)=\sum_{k\neq i}t_{ik}(n)f_{kj}.$

It is said the matrix $F$ to be null-recurrent if

$\sum_{n\geq 1}nt_{ii}(n)\lambda^{-n}<\infty;$

otherwise, $F$ is called positive recurrent.

The theorem below is a generalization of the classic Perron-Frobenius theory
to non-negative infinite matrices. We refer the reader to [Kit98] (Theorem
$7.1.3$) for a detailed proof.

######  Theorem 7.2 (Generalized Perron-Frobenius theorem).

Let $F$ be an irreducible, aperiodic, recurrent, non-negative, infinite
matrix. Then there exists a Perron-Frobenius eigenvalue

$\lambda=\lim_{n\to\infty}(f^{(n)}_{ij})^{\frac{1}{n}}>0$

(assumed to be finite) such that:

$(a)$ there exist strictly positive left $\ell$ and right $r$ eigenvectors for
$\lambda$;

$(b)$ both $\ell$ and $r$ are unique up to multiplication by constants;

$(c)$ $F$ is positive recurrent if and only if $\ell\cdot
r=\sum_{i}\ell_{i}r_{i}<\infty$;

$(d)$ if $F$ is null-recurrent, then
$\displaystyle{\lim_{n\to\infty}F^{n}\lambda^{-n}=0}$;

$(e)$ if $F$ is positive recurrent, then
$\displaystyle{\lim_{n\to\infty}F^{n}\lambda^{-n}=r\ell}$ (normalized so that
$\ell r=\textbf{1}$).

######  Remark 7.3.

The aperiodicity assumption can be removed from the statement of Theorem 7.2
(see [Kit98] Lemma $7.1.37$ and Lemma $7.1.38$). Hence all the results in this
section are true without assuming aperiodicity. But to be consistent with the
literature we have stated the results keeping the aperiodicity assumption.

The following result (proved in [BJ21]) provides an explicit formula for a
tail invariant measure on the path space of a stationary generalized Bratteli
diagram. Since this result is crucial for rest of the paper, we reproduce the
proof for completion.

######  Theorem 7.4 (Theorem 2.20, [BJ21]).

Let $B=B(F)$ be a stationary generalized Bratteli diagram such that the
incidence matrix $F$ is irreducible, aperiodic and recurrent. Then

$(1)$ there exists a tail invariant measure $\mu$ on the path space $Y_{B}$,

$(2)$ the measure $\mu$ is finite if and only if the left Perron-Frobenius
eigenvector $\ell=(\ell_{v})$ has the property $\sum_{v}\ell_{v}<\infty$.

###### Proof.

We identify the sets $V_{i}$ with a countably infinite set $V$. Since $F$ is
irreducible, aperiodic, and recurrent, there exists a Perron-Frobenius
eigenvalue $\lambda$ for $F$ (see Theorem 7.2). We denote by $\ell=(\ell_{v})$
a left eigenvector corresponding to $\lambda$ indexed by elements of $V$. Let
$\overline{e}(w,v)$ denote a finite path that begins at $w\in V_{0}$ and ends
at $v\in V_{n}$, $n\in{\mathbb{N}}$. To define the measure $\mu$, we find its
values on all cylinder sets, and then we check that this definition can be
extended to a Borel measure using the Kolmogorov consistency theorem. For the
cylinder set $[\overline{e}(w,v)]$, we set

$\mu([\overline{e}(w,v)])=\frac{\ell_{v}}{\lambda^{n}}.$ (7.1)

To see that $\mu$ can be extended to a Borel measure, let
$\overline{g}_{u}=\overline{e}(w,v)e(v,u)$ denote the concatenation of path
$\overline{e}(w,v)$ with an edge $e(v,u)$ where $u\in V_{n+1}\cap
r(s^{-1}(v))$. Next, we compute the measure of the set

$\bigcup_{u\in V_{n+1}\cap r(s^{-1}(v))}[\overline{g}_{u}]$

and show that it is equal to the measure of the set $[e(w,v)]$. For this, we
use the relation $\ell F=\lambda\ell$:

$\mu\Big{(}\bigcup_{u\in V_{n+1}\cap
r(s^{-1}(v))}[\overline{g}_{u}]\Big{)}=\sum_{u\in
V_{n+1}}f_{uv}\frac{l_{u}}{\lambda^{n+1}}=\frac{\ell_{v}}{\lambda^{n}}=\mu([\overline{e}(w,v)]).$

Measure $\mu$ is tail invariant since any two cylinder sets defined by finite
paths terminating at the same vertex $v\in V_{n}$ (say (say
$\overline{e}(w_{1},v)$ and $\overline{e}(w_{2},v)$) ) have same measure as
given by

$\mu([\overline{e}(w_{1},v)])=\frac{\ell_{v}}{\lambda^{n}}=\mu([\overline{e}(w_{2},v)]).$

This proves part $(1)$ of the theorem.

To see that $(2)$ holds, we observe that the set $Y_{B}$ is the union of all
subsets $Y_{B}(w)$ where $Y_{B}(w)=\\{x=(x_{i})\in Y_{B}:s(x_{0})=w\\}$. Then

$\mu(Y_{B})=\sum_{w\in V_{0}}\mu(Y_{B}(w))=\sum_{v\in V}\ell_{v}.$

The measure $\mu$ is finite if and only if $\sum_{v\in V}\ell_{v}<\infty$. ∎

A special case of a recurrent matrix is positive recurrent. If we assume that
the incidence matrix $F$ is positive recurrent and has the equal row sum
property, then the tail invariant measure defined above is always finite.

######  Corollary 7.5.

Let $B=B(F)$ be a stationary generalized Bratteli diagram such that the
incidence matrix $F$ is irreducible, aperiodic and positive recurrent. Assume
that $F$ has equal row sum property, i.e. for every $v,v^{\prime}\in V$,

$\sum_{w\in V}f_{v,w}=\sum_{w\in V}f_{v^{\prime},w}.$

Then the tail invariant measure $\mu$ (defined in (7.1)) on the path-space
$Y_{B}$ is finite.

###### Proof.

Since $F$ is positive recurrent, we have

$\ell\cdot r=\sum_{v\in V}\ell_{v}r_{v}<\infty,$

where $r$ denotes the right eigenvector corresponding to $\lambda$. Moreover,
the equal row sum property implies that we can take $r=(...1,1,1,...)$. Hence

$\mu(Y_{B})=\sum_{i\in{\mathbb{Z}}}\ell_{i}<\infty.$

∎

###  7.2. From tail invariant measure to shift invariant measure

In Subsection 7.1, we have provided an explicit formula for a tail invariant
(or invariant under the Vershik map) measure on a stationary generalized
Bratteli diagram with an irreducible, aperiodic, and recurrent incidence
matrix. In this subsection, we will use the isomorphism between the subshift
(associated with a bounded size left determined substitution on a countably
infinite alphabet) and the Vershik map on path space of the corresponding
stationary generalized ordered Bratteli diagram (see Theorem 6.13) to obtain a
shift invariant measure.

Note that if $\sigma$ is the substitution read on a stationary generalized
Bratteli diagram $B=B(F)$ (see Remark 6.11) then the infinite substitution
matrix of $\sigma$ (see Definition 2.1) is same as the incidence matrix $F$.

The main result of this section is the following:

######  Theorem 7.6.

Let $\sigma$ be a bounded size left determined substitution on a countably
infinite alphabet ${\mathcal{A}}$ and $(X_{\sigma},T)$ be the corresponding
subshift. Assume that the countably infinite substitution matrix $M$ is
irreducible, aperiodic, and recurrent. Then

$(1)$ there exists a shift invariant measure $\nu$ on $X_{\sigma}$;

$(2)$ the measure $\nu$ is finite if and only if the Perron-Frobenius left
eigenvector $\ell=(\ell_{i})$ has the property $\sum_{i}\ell_{i}<\infty$.

###### Proof.

By Theorem 6.13, there exists a stationary generalized Bratteli diagram $B(F)$
such that $(X_{\sigma},T)$ is isomorphic to the dynamical system
$(Y_{B},\varphi)$. Let $f:(X_{\sigma},T_{\sigma})\rightarrow(Y_{B},\varphi)$
implement this isomorphism. Also, by construction, the incidence matrix $F$ of
the diagram coincides with the substitution matrix $M$ (see Section 6.2).
Since $M$ is irreducible and recurrent, there exists a tail invariant measure
$\mu$ on the path space $Y_{B}$ (Theorem 7.4). We define the measure $\nu$ on
$X_{\sigma}$ by setting

$\nu(A)=\mu\circ f(A)$ (7.2)

where $A\subset X_{\sigma}$ is a Borel set. The rest of the proof is obvious.
∎

######  Corollary 7.7.

Let $\sigma$ be a constant length left determined substitution on a countably
infinite alphabet such that the substitution matrix $M$ is irreducible,
aperiodic, and positive recurrent. Then the shift invariant measure $\nu$ on
$X_{\sigma}$ defined in (7.2) is finite.

######  Remark 7.8.

In a sequel to this paper we show that if $B=B(F)$ be a stationary generalized
Bratteli diagram with irreducible, aperiodic and positive recurrent incidence
matrix $F$ then the shift-invariant finite measure (defined in (7.1)) on the
path-space $Y_{B}$ is ergodic. The proof involves a direct application of the
pointwise ergodic theorem. Since we prove it more generality in the upcoming
sequel we have not mentioned the proof here.

As a consequence for a bounded size, left determined substitution $\sigma$ (on
a countably infinite alphabet) with irreducible, aperiodic and positive
recurrent substitution matrix the shift invariant finite measure $\nu$ on
$X_{\sigma}$ defined in (7.2) is ergodic.

##  8\. Examples

In this section we provide some examples of bounded size, left determined
substitution on countably infinite alphabets for which stationary generalized
Bratteli-Vershik can be constructed using methods in Section 6.

######  Example 8.1.

One step forward, two step back substitution on ${\mathbb{Z}}$. Define
$\sigma$ by

$\textbf{-1}\mapsto-2-1\,\,\,0\,\,\,;\,\,\,\textbf{0}\mapsto-1\,\,\,0\,\,1$
$n\mapsto(n-1)(n+1)(n+1)\,\,;\,\,n\leq-2$
$n\mapsto(n-1)(n-1)(n+1)\,\,;\,\,n\geq 1$

This substitution is bounded size and left determined, hence by Theorem 6.13
there exists a stationary generalized Bratteli-Vershik model for the
associated subshift. Figure 2 shows part of $V_{n}$, $E_{n}$ and $V_{n+1}$ for
any $n\in{\mathbb{N}}_{0}$ of the stationary generalized Bratteli-Vershik
model.

Figure 2. Generalized B-V model for Example 8.1.

Since the substitution matrix is irreducible, aperiodic and recurrent, we can
apply Theorem 7.6 to obtain an expression for a shift invariant measure.
Manual calculation yields P.F value $\lambda=3$ and the left P.F eigenvector
is given by

$\ell=(...\frac{1}{2^{4}},\frac{1}{2^{3}},\frac{1}{2^{2}},\frac{1}{2},1,1,\frac{1}{2},\frac{1}{2^{2}},\frac{1}{2^{3}}.....).$

The right P.F eigenvector has all entries equal to $1$. By normalizing the
left P.F eigenvector such that $\sum_{v}\ell_{v}=1$, we obtain a probability
shift-invariant measure $\nu$ (defined in (7.2)) on the associated subshift.

######  Example 8.2.

The squared one step forward, two step backwards, substitution on
$2{\mathbb{Z}}$. Define $\sigma$ by

$\textbf{-2}\mapsto-4-4\,-2-2-2\,\,-4-2-2\,\,0;\,\,\,\textbf{0}\mapsto-200022002$
$n\mapsto(n-2)(n-2)n(n-2)(n-2)nnn(n+2)\,\,\textrm{for}\,\,n\in
2{\mathbb{Z}}\setminus\\{0,-2\\}$

This substitution is again bounded size and left determined, thus by Theorem
6.13 there exists a stationary generalized Bratteli-Vershik model for the
associated subshift. Note that the substitution matrix is irreducible,
aperiodic and recurrent, hence we can apply Theorem 7.6 to obtain expression
for a shift invariant measure. By manual calculations, we get $\lambda=9$. The
left P.F eigenvector is given by

$\ell=(...\frac{1}{2^{8}},\frac{1}{2^{6}},\frac{1}{2^{4}},\frac{1}{2^{2}},\frac{1}{3},\frac{1}{3},\frac{1}{2^{2}},\frac{1}{2^{4}},\frac{1}{2^{6}},\frac{1}{2^{8}}.....).$

The right P.F eigenvector has all entries equal to $1$. By normalizing the
left P.F eigenvector such that $\sum_{v}\ell_{v}=1$, we obtain a probability
shift-invariant measure $\nu$ (defined in (7.2)) on the associated subshift.

The next two examples have recurrent substitution matrix with the sum
$\sum_{v}\ell_{v}=\infty$. Hence the shift-invariant measure is sigma-finite.

######  Example 8.3.

Random walk on ${\mathbb{Z}}$. Define $\sigma$ by

$n\mapsto(n-1)(n+1)$

Note that random walk on ${\mathbb{Z}}$ is a bounded size, left determined
substitution, hence by Theorem 6.13 there exists a stationary generalized
Bratteli-Vershik model for the associated subshift. Figure 3 shows part of
$V_{n}$, $E_{n}$ and $V_{n+1}$ for any $n\in{\mathbb{N}}_{0}$ of the
stationary generalized Bratteli-Vershik model.

Figure 3. Generalized B-V model of the Random walk on ${\mathbb{Z}}$.

The substitution matrix is irreducible, periodic with period 2 and null
recurrent. Although the matrix in not aperiodic, we can still study the
substitution (see Remark 7.3). Manual calculation yields P.F value $\lambda=2$
and both the left and right P.F eigenvectors are given by

$r=\ell=(.....\frac{1}{2},\frac{1}{2},\frac{1}{2},\frac{1}{2},.....).$

Hence by Theorem 7.6, the shift-invariant measure $\nu$ (defined in (7.2)) on
$X_{\sigma}$ is a sigma-finite, infinite measure.

######  Example 8.4.

Squared drunken man substitution on $2{\mathbb{Z}}$. Define $\sigma$ by

$n\mapsto(n-2)nn(n+2)\,\,;\,\,\,n\in 2{\mathbb{Z}}$

This substitution is also bounded size and left determined, hence by Theorem
6.13 there exists a stationary generalized Bratteli-Vershik model for the
associated subshift. The substitution matrix is irreducible, aperiodic and
recurrent, hence we can apply Theorem 7.6 to obtain the expression for a shift
invariant measure. Manual calculation shows P.-F. value $\lambda=4$ and both
the left and right P.F eigenvectors are given by

$r=\ell=(.....1,1,1,1,1,....).$

Thus by Theorem 7.6, the shift-invariant measure $\nu$ (defined in (7.2)) on
$X_{\sigma}$ is a sigma-finite, infinite measure.

Acknowledgments The authors are pleased to thank Olena Karpel for many helpful
discussions. We also thank the colleagues at the University of Iowa, USA and
Ben Gurion University of the Negev, Israel for fruitful discussions and
support.

## References

  * [BDK06] S. Bezuglyi, A. H. Dooley, and J. Kwiatkowski.  Topologies on the group of Borel automorphisms of a standard Borel space.  Topol. Methods Nonlinear Anal., 27(2):333–385, 2006.
  * [BJ21] Sergey Bezuglyi and Palle E. T. Jorgensen.  Harmonic analysis invariants for infinite graphs via operators and algorithms.  J. Fourier Anal. Appl., 27(2):Paper No. 34, 46, 2021.
  * [BK96] H. Becker and A. S. Kechris.  The descriptive set theory of Polish group actions, volume 232 of London Mathematical Society Lecture Note Series.  Cambridge University Press, Cambridge, 1996.
  * [BKM09] S. Bezuglyi, J. Kwiatkowski, and K. Medynets.  Aperiodic substitution systems and their Bratteli diagrams.  Ergodic Theory Dynam. Systems, 29(1):37–72, 2009.
  * [BKMS10] S. Bezuglyi, J. Kwiatkowski, K. Medynets, and B. Solomyak.  Invariant measures on stationary Bratteli diagrams.  Ergodic Theory Dynam. Systems, 30(4):973–1007, 2010.
  * [Bra72] Ola Bratteli.  Inductive limits of finite dimensional $C^{\ast}$-algebras.  Trans. Amer. Math. Soc., 171:195–234, 1972.
  * [BSTY19] Valérie Berthé, Wolfgang Steiner, Jörg M. Thuswaldner, and Reem Yassawi.  Recognizability for sequences of morphisms.  Ergodic Theory Dynam. Systems, 39(11):2896–2931, 2019.
  * [Cas94] Julien Cassaigne.  An algorithm to test if a given circular HD0L-language avoids a pattern.  In Information processing ’94, Vol. I (Hamburg, 1994), IFIP Trans. A Comput. Sci. Tech., A-51, pages 459–464. North-Holland, Amsterdam, 1994.
  * [DHS99] F. Durand, B. Host, and C. Skau.  Substitutional dynamical systems, Bratteli diagrams and dimension groups.  Ergodic Theory Dynam. Systems, 19(4):953–993, 1999.
  * [DJK94] R. Dougherty, S. Jackson, and A. S. Kechris.  The structure of hyperfinite Borel equivalence relations.  Trans. Amer. Math. Soc., 341(1):193–225, 1994.
  * [DK19] Tomasz Downarowicz and Olena Karpel.  Decisive Bratteli-Vershik models.  Studia Math., 247(3):251–271, 2019.
  * [Dom12] Daniel Dombek.  Substitutions over infinite alphabet generating $(-\beta)$-integers.  Internat. J. Found. Comput. Sci., 23(8):1627–1639, 2012.
  * [DOP18] Fabien Durand, Nicholas Ormes, and Samuel Petite.  Self-induced systems.  J. Anal. Math., 135(2):725–756, 2018.
  * [Dur10] Fabien Durand.  Combinatorics on Bratteli diagrams and dynamical systems.  In Combinatorics, automata and number theory, volume 135 of Encyclopedia Math. Appl., pages 324–372. Cambridge Univ. Press, Cambridge, 2010.
  * [Fer06] Sébastien Ferenczi.  Substitution dynamical systems on infinite alphabets.  Ann. Inst. Fourier (Grenoble), 56:2315–2343, 2006.
  * [FM77] Jacob Feldman and Calvin C. Moore.  Ergodic equivalence relations, cohomology, and von Neumann algebras. I.  Trans. Amer. Math. Soc., 234(2):289–324, 1977.
  * [For97] A. H. Forrest.  $K$-groups associated with substitution minimal systems.  Israel J. Math., 98:101–139, 1997.
  * [GPS95] Thierry Giordano, Ian F. Putnam, and Christian F. Skau.  Topological orbit equivalence and $C^{*}$-crossed products.  J. Reine Angew. Math., 469:51–111, 1995.
  * [Gra11] Robert M. Gray.  Entropy and information theory.  Springer, New York, second edition, 2011.
  * [GS98] B. M. Gurevich and S. V. Savchenko.  Thermodynamic formalism for symbolic Markov chains with a countable number of states.  Uspekhi Mat. Nauk, 53(2(320)):3–106, 1998.
  * [GW95] Eli Glasner and Benjamin Weiss.  Weak orbit equivalence of Cantor minimal systems.  Internat. J. Math., 6(4):559–579, 1995.
  * [Hjo00] Greg Hjorth.  Classification and orbit equivalence relations, volume 75 of Mathematical Surveys and Monographs.  American Mathematical Society, Providence, RI, 2000.
  * [HPS92] Richard H. Herman, Ian F. Putnam, and Christian F. Skau.  Ordered Bratteli diagrams, dimension groups and topological dynamics.  Internat. J. Math., 3(6):827–864, 1992.
  * [JKL02] S. Jackson, A. S. Kechris, and A. Louveau.  Countable Borel equivalence relations.  J. Math. Log., 2(1):1–80, 2002.
  * [JKL14] Johannes Jaerisch, Marc Kesseböhmer, and Sanaz Lamei.  Induced topological pressure for countable state Markov shifts.  Stoch. Dyn., 14(2):1350016, 31, 2014.
  * [Kec95] Alexander S. Kechris.  Classical descriptive set theory, volume 156 of Graduate Texts in Mathematics.  Springer-Verlag, New York, 1995.
  * [Kec19] Alexander S. Kechris.  The theory of countable borel equivalence relations.  preprint, 2019.
  * [Kit98] Bruce P. Kitchens.  Symbolic dynamics.  Universitext. Springer-Verlag, Berlin, 1998.  One-sided, two-sided and countable state Markov shifts.
  * [KM04] Alexander S. Kechris and Benjamin D. Miller.  Topics in orbit equivalence, volume 1852 of Lecture Notes in Mathematics.  Springer-Verlag, Berlin, 2004.
  * [KS19] Karel Klouda and Štěpán Starosta.  Characterization of circular D0L-systems.  Theoret. Comput. Sci., 790:131–137, 2019.
  * [Mar73] John C. Martin.  Minimal flows arising from substitutions of non-constant length.  Math. Systems Theory, 7:72–82, 1973.
  * [Mau06] Christian Mauduit.  Propriétés arithmétiques des substitutions et automates infinis.  Annales de l’Institut Fourier, 56(7):2525–2549, 2006.
  * [Med06] Konstantin Medynets.  Cantor aperiodic systems and Bratteli diagrams.  C. R. Math. Acad. Sci. Paris, 342(1):43–46, 2006.
  * [Mos92] Brigitte Mossé.  Puissances de mots et reconnaissabilité des points fixes d’une substitution.  Theoret. Comput. Sci., 99(2):327–334, 1992.
  * [Mos96] Brigitte Mossé.  Reconnaissabilité des substitutions et complexité des suites automatiques.  Bull. Soc. Math. France, 124(2):329–346, 1996.
  * [MRW21] Neil Mañibo, Dan Rust, and James J. Walton.  Spectral properties of substitutions on compact alphabets, 2021.
  * [MS93] Filippo Mignosi and Patrice Séébold.  If a DOL language is $k$-power free then it is circular.  In Automata, languages and programming (Lund, 1993), volume 700 of Lecture Notes in Comput. Sci., pages 507–518. Springer, Berlin, 1993\.
  * [Nad13] M. G. Nadkarni.  Basic ergodic theory, volume 6 of Texts and Readings in Mathematics.  Hindustan Book Agency, New Delhi, third edition, 2013.
  * [OTW14] William Ott, Mark Tomforde, and Paulette N. Willis.  One-sided shift spaces over infinite alphabets, volume 5 of New York Journal of Mathematics. NYJM Monographs.  State University of New York, University at Albany, Albany, NY, 2014.
  * [PFS14] Natalie Priebe Frank and Lorenzo Sadun.  Fusion tilings with infinite local complexity.  Topology Proc., 43:235–276, 2014.
  * [RY17] Eric Rowland and Reem Yassawi.  Profinite automata.  Adv. in Appl. Math., 85:60–83, 2017.
  * [Shi20] Takashi Shimomura.  Bratteli-Vershik models and graph covering models.  Adv. Math., 367:107127, 54, 2020.
  * [Sol98] B. Solomyak.  Nonperiodicity implies unique composition for self-similar translationally finite tilings.  Discrete Comput. Geom., 20(2):265–279, 1998.
  * [Tak20] Hiroki Takahasi.  Entropy-approachability for transitive Markov shifts over infinite alphabet.  Proc. Amer. Math. Soc., 148(9):3847–3857, 2020.
  * [Var63] V. S. Varadarajan.  Groups of automorphisms of Borel spaces.  Trans. Amer. Math. Soc., 109:191–220, 1963.
  * [Ver81] A. M. Vershik.  Uniform algebraic approximation of shift and multiplication operators.  Dokl. Akad. Nauk SSSR, 259(3):526–529, 1981.
  * [Wei84] Benjamin Weiss.  Measurable dynamics.  In Conference in modern analysis and probability (New Haven, Conn., 1982), volume 26 of Contemp. Math., pages 395–421. Amer. Math. Soc., Providence, RI, 1984.