\documentclass[numbers=enddot,12pt,final,onecolumn,notitlepage]{scrartcl}%
\usepackage[headsepline,footsepline,manualmark]{scrlayer-scrpage}
\usepackage[all,cmtip]{xy}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{framed}
\usepackage{amsmath}
\usepackage{comment}
\usepackage{color}
\usepackage{hyperref}
\usepackage[sc]{mathpazo}
\usepackage[T1]{fontenc}
\usepackage{amsthm}
%TCIDATA{OutputFilter=latex2.dll}
%TCIDATA{Version=5.50.0.2960}
%TCIDATA{LastRevised=Sunday, June 30, 2019 01:31:04}
%TCIDATA{SuppressPackageManagement}
%TCIDATA{<META NAME="GraphicsSave" CONTENT="32">}
%TCIDATA{<META NAME="SaveForMode" CONTENT="1">}
%TCIDATA{BibliographyScheme=Manual}
%BeginMSIPreambleData
\providecommand{\U}[1]{\protect\rule{.1in}{.1in}}
%EndMSIPreambleData
\theoremstyle{definition}
\newtheorem{theo}{Theorem}[section]
\newenvironment{theorem}[1][]
{\begin{theo}[#1]\begin{leftbar}}
{\end{leftbar}\end{theo}}
\newtheorem{lem}[theo]{Lemma}
\newenvironment{lemma}[1][]
{\begin{lem}[#1]\begin{leftbar}}
{\end{leftbar}\end{lem}}
\newtheorem{prop}[theo]{Proposition}
\newenvironment{proposition}[1][]
{\begin{prop}[#1]\begin{leftbar}}
{\end{leftbar}\end{prop}}
\newtheorem{defi}[theo]{Definition}
\newenvironment{definition}[1][]
{\begin{defi}[#1]\begin{leftbar}}
{\end{leftbar}\end{defi}}
\newtheorem{remk}[theo]{Remark}
\newenvironment{remark}[1][]
{\begin{remk}[#1]\begin{leftbar}}
{\end{leftbar}\end{remk}}
\newtheorem{coro}[theo]{Corollary}
\newenvironment{corollary}[1][]
{\begin{coro}[#1]\begin{leftbar}}
{\end{leftbar}\end{coro}}
\newtheorem{conv}[theo]{Convention}
\newenvironment{condition}[1][]
{\begin{conv}[#1]\begin{leftbar}}
{\end{leftbar}\end{conv}}
\newtheorem{quest}[theo]{Question}
\newenvironment{algorithm}[1][]
{\begin{quest}[#1]\begin{leftbar}}
{\end{leftbar}\end{quest}}
\newtheorem{warn}[theo]{Warning}
\newenvironment{conclusion}[1][]
{\begin{warn}[#1]\begin{leftbar}}
{\end{leftbar}\end{warn}}
\newtheorem{conj}[theo]{Conjecture}
\newenvironment{conjecture}[1][]
{\begin{conj}[#1]\begin{leftbar}}
{\end{leftbar}\end{conj}}
\newtheorem{exmp}[theo]{Example}
\newenvironment{example}[1][]
{\begin{exmp}[#1]\begin{leftbar}}
{\end{leftbar}\end{exmp}}
\iffalse
\newenvironment{proof}[1][Proof]{\noindent\textbf{#1.} }{\ \rule{0.5em}{0.5em}}
\fi
\newenvironment{verlong}{}{}
\newenvironment{vershort}{}{}
\newenvironment{noncompile}{}{}
\excludecomment{verlong}
\includecomment{vershort}
\excludecomment{noncompile}
\newcommand{\kk}{\mathbf{k}}
\newcommand{\id}{\operatorname{id}}
\newcommand{\ev}{\operatorname{ev}}
\newcommand{\Comp}{\operatorname{Comp}}
\newcommand{\bk}{\mathbf{k}}
\newcommand{\Nplus}{\mathbb{N}_{+}}
\newcommand{\NN}{\mathbb{N}}
\let\sumnonlimits\sum
\let\prodnonlimits\prod
\renewcommand{\sum}{\sumnonlimits\limits}
\renewcommand{\prod}{\prodnonlimits\limits}
\DeclareSymbolFont{bbold}{U}{bbold}{m}{n}
\DeclareSymbolFontAlphabet{\mathbbold}{bbold}
\setlength\textheight{22.5cm}
\setlength\textwidth{15cm}
\ihead{Errata to ``Enumerative Combinatorics on Words''}
\ohead{\today}
\begin{document}

\begin{center}
\textbf{Chapter 1: Enumerative Combinatorics on Words}

\textit{Dominique Perrin and Antonio Restivo}

\url{http://www-igm.univ-mlv.fr/~perrin/Recherche/Publications/BookChapters/enhandbook.pdf}

version of 10 July 2014

\textbf{Errata and addenda by Darij Grinberg}

\bigskip
\end{center}

%\setcounter{section}{}


\section{Errata}

The numbering of pages in the following errata matches the numbering of pages
on the paper (not the numbering of pages in the PDF file).

I have read this chapter from its beginning to \S 1.5.2 (except for a few
tangential examples and remarks). This part of the chapter should be covered
(almost) completely by these errata. My comments on the rest of the chapter
are spotty and random.

\begin{itemize}
\item \textbf{page 7:} \textquotedblleft its links with several connexions
with\textquotedblright\ should probably just be \textquotedblleft its links
with\textquotedblright\ or \textquotedblleft several connexions
with\textquotedblright.

\item \textbf{page 8:} \textquotedblleft well-kown\textquotedblright%
\ $\rightarrow$ \textquotedblleft well-known\textquotedblright.

\item \textbf{page 9:} I would put the words \textquotedblleft radix
order\textquotedblright\ in italics, since you are just defining this concept
here. Also, I would point out that this \textquotedblleft radix
order\textquotedblright\ is better known as the length-lexicographic order.

\item \textbf{page 9:} I would add the following remark: For any $n\geq0$, the
set $A^{n}$ of $n$-tuples of elements of $A$ is identified with a subset of
$A^{\ast}$ (indeed, every $n$-tuple $\left(  a_{1},a_{2},\ldots,a_{n}\right)
\in A^{n}$ is identified with the word $a_{1}a_{2}\cdots a_{n}\in A^{\ast}$).
This explains how \textquotedblleft$X\cap A^{n}$\textquotedblright\ is to be
understood in \S 1.2.1, and similar expressions elsewhere.

\item \textbf{page 10:} \textquotedblleft the the product\textquotedblright%
\ $\rightarrow$ \textquotedblleft that the product\textquotedblright.

\item \textbf{page 10:} Somewhere here it would be helpful to define the
notation $X^{\ast}$. (Namely, if $X$ is a subset of $A^{\ast}$, then $X^{\ast
}$ denotes the submonoid of $A^{\ast}$ generated by $X$. This is not always a
free monoid, so this is not a particular case of the notation $A^{\ast}$
defined on page 8.)

\item \textbf{page 10:} Add a period at the end of the equality (1.2.3).

\item \textbf{page 11, Example 2:} \textquotedblleft and $y\in aD_{a}^{\ast}%
b$\textquotedblright\ $\rightarrow$ \textquotedblleft and $y\in D_{a}^{\ast}$,
so that $d\in aD_{a}^{\ast}b$\textquotedblright.

\item \textbf{page 11, Example 2:} Remove the period at the end of equation
(1.2.6) (the sentence does not end here).

\item \textbf{page 11, Example 2:} Add periods at the end of equation (1.2.7)
and at the end of equation (1.2.8).

\item \textbf{page 12:} Between (1.2.8) and (1.2.9), the \textquotedblleft%
$n4^{n}$\textquotedblright\ should be in parentheses (since both $n$ and
$4^{n}$ are meant to be part of the denominator).

\item \textbf{page 12, Example 3:} \textquotedblleft The initial edges are
indicated with an incoming edge and the terminal ones with with an outgoing
edge\textquotedblright\ $\rightarrow$ \textquotedblleft The initial states are
indicated with an incoming arrow and the terminal ones with an outgoing
arrow\textquotedblright. (There are too many mistakes in this sentence to list.)

\item \textbf{page 13, Example 5:} In the equation \textquotedblleft$M=\left[
%
\begin{array}
[c]{cc}%
F_{n+1} & F_{n}\\
F_{n} & F_{n-1}%
\end{array}
\right]  $\textquotedblright, replace \textquotedblleft$M$\textquotedblright%
\ by \textquotedblleft$M^{n}$\textquotedblright.

\item \textbf{page 14, proof of Proposition 2:} Replace \textquotedblleft%
$n/d\geq p/d+q/d$\textquotedblright\ by \textquotedblleft$n/d\geq
p/d+q/d-1$\textquotedblright.

\item \textbf{page 14, Example 6:} You write \textquotedblleft$x_{n-4}y_{n-3}$
is a prefix of $x_{n-3}$ and thus of $x_{n-1}$\textquotedblright. The first
part of this is wrong ($x_{n-4}y_{n-3}$ is usually too long to be a prefix of
$x_{n-3}$). The second is correct, but needs to be proven. Here is a sketch of
the proof:

Forget that we fixed $n$. First, it is clear that%
\begin{equation}
y_{n+1}=x_{n}y_{n-1}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq4.
\label{p14.fib.yxy.0}%
\end{equation}
(Indeed, this follows by removing the last two letters from the equality
$x_{n+1}=x_{n}x_{n-1}$.) Next, we claim that%
\begin{equation}
y_{n+1}=x_{n-1}y_{n}\ \ \ \ \ \ \ \ \ \ \text{for each }n\geq3.
\label{p14.fib.yxy.1}%
\end{equation}


(\textit{Proof of (\ref{p14.fib.yxy.1}):} We proceed by induction on $n$. In
the case $n=3$, the equality (\ref{p14.fib.yxy.1}) holds because both $y_{4}$
and $x_{2}y_{3}$ equal $a$. This covers the induction base. For the induction
step, we fix an integer $m\geq4$, and we assume that (\ref{p14.fib.yxy.1})
holds for $n=m-1$. We must now prove that (\ref{p14.fib.yxy.1}) holds for
$n=m$.

We have assumed that (\ref{p14.fib.yxy.1}) holds for $n=m-1$. In other words,
we have $y_{m}=x_{m-2}y_{m-1}$. But the recursive definition of the Fibonacci
sequence of words yields $x_{m}=x_{m-1}x_{m-2}$. Now, (\ref{p14.fib.yxy.0})
(applied to $n=m$) yields $y_{m+1}=\underbrace{x_{m}}_{=x_{m-1}x_{m-2}}%
y_{m-1}=x_{m-1}\underbrace{x_{m-2}y_{m-1}}_{=y_{m}}=x_{m-1}y_{m}$. In other
words, (\ref{p14.fib.yxy.1}) holds for $n=m$. This completes the induction
step. Thus, (\ref{p14.fib.yxy.1}) is proven by induction.)

Now, assume that $n\geq6$. Then, (\ref{p14.fib.yxy.1}) (applied to $n-3$
instead of $n$) yields $y_{n-2}=x_{n-4}y_{n-3}$. Hence, $x_{n-4}y_{n-3}$ is a
prefix of $x_{n-2}$ (since $y_{n-2}$ is clearly a prefix of $x_{n-2}$) and
thus also a prefix of $x_{n-1}$ (since $x_{n-1}=x_{n-2}x_{n-3}$). This
completes the proof of your claim.

\item \textbf{page 14, \S 1.3.1:} You write: \textquotedblleft The conjugacy
class of a word of length $n$ and period $p$ has $p$ elements if $p$ divides
$n$ and has $n$ elements otherwise.\textquotedblright. Here you probably mean
\textquotedblleft minimal period\textquotedblright\ rather than
\textquotedblleft period\textquotedblright, since otherwise this is clearly
false. But I'm not sure how to prove it when $p$ is the minimum period either.
(Fortunately you don't actually use this observation; Proposition 3 is clear
for simpler reasons.)

\item \textbf{page 14, \S 1.3.2:} The notions of a \textit{primitive necklace}
(= a necklace consisting of primitive words) and of the \textit{length} of a
necklace (= the length of any word in it) should be defined. Also, it should
be explained what you mean by \textquotedblleft on $k$
letters\textquotedblright\ (namely, you mean that you are working over a
$k$-letter alphabet $A$; you are not requiring that all its $k$ letters are
actually being used in the necklace).

\item \textbf{page 14, \S 1.3.2:} Add a period after the equality (1.3.11).

\item \textbf{page 15:} \textquotedblleft The \textit{M\"{o}bius function} is
defined\textquotedblright\ $\rightarrow$ \textquotedblleft The
\textit{M\"{o}bius function} is the function $\mu:\mathbb{N}\setminus
0\rightarrow\mathbb{Z}$ defined\textquotedblright. (Otherwise, the
\textquotedblleft$\mu$\textquotedblright\ in the equality is out of place.)

\item \textbf{page 16:} It makes sense to mention that the convolution product
of functions $\mathbb{N}\setminus0\rightarrow R$ is commutative whenever $R$
is commutative. (You use this tacitly.)

\item \textbf{page 16, proof of Proposition 4:} At the very end of the proof,
replace \textquotedblleft$\sum_{n=de}\mu\left(  d\right)  k^{e}$%
\textquotedblright\ by \textquotedblleft$\sum_{n=de}k^{d}\mu\left(  e\right)
$\textquotedblright\ (this is equivalent, but closer to what you get from the
convolution product, and also closer to the expression you want).

\item \textbf{page 17:} \textquotedblleft the set $M_{d}$ of integers $m\leq
n$\textquotedblright\ $\rightarrow$ \textquotedblleft the set $M_{d}$ of
positive integers $m\leq n$\textquotedblright.

\item \textbf{page 17, proof of Proposition 6:} It is not clear what you mean
by \textquotedblleft the multiset formed by the $n$ circular shifts of the
words of length $n$\textquotedblright. The obvious interpretation would be to
consider both the two shifts $12$ and $21$ of the word $12$ and also the two
shifts $21$ and $12$ of the word $21$; but this is not what you mean. Instead,
the multiset you want is the multiset obtained by picking a representative of
each necklace (of length $n$ on $k$ letters), and then writing down all $n$
cyclic shifts of each necklace you have picked. (When the necklace is not
primitive, there will be repetitions among its shifts, whence you get a
multiset, not a set.)

\item \textbf{page 17, proof of Proposition 6:} When you defined periods of a
word, you required them to be positive integers. Here, you are using $0$ as a
period of a word. Either this or the definition of a period needs to be
modified (although it shouldn't be difficult to do so).

\item \textbf{page 18, \S 1.3.3:} \textquotedblleft has a unique
factorization\textquotedblright\ $\rightarrow$ \textquotedblleft has at most
one factorization\textquotedblright.

I would furthermore illustrate this notion of a \textquotedblleft
factorization\textquotedblright\ of a necklace by a picture: If we draw out
the necklace on a circle, then a factorization means a way of partitioning
this circle into arcs (with each arc starting and ending in the middle between
two consecutive letters) such that each arc gives a word in $X$ (when you read
the letters on this arc in clockwise order). Such factorizations are
considered equal when the corresponding arcs are the same (or, more precisely:
the points where one arc ends and the next one begins are the same). Thus,
$\left\{  aa\right\}  $ is not a circular code (since the necklace
corresponding to the word $aaaa$ has two different factorizations; these
factorizations are different even though the factors are all the same!), and
$\left\{  aba,aabaa\right\}  $ is not a circular code either (since the
necklace $baaabaaa$ has two factorizations: either of the two
\textquotedblleft$b$\textquotedblright s can be part of an \textquotedblleft%
$aba$\textquotedblright\ factor or part of an \textquotedblleft$aabaa$%
\textquotedblright\ factor).

\item \textbf{page 18, \S 1.3.3:} I think you want to require circular codes
to consist of \textbf{nonempty} words. Otherwise, the \textquotedblleft
Formally\textquotedblright\ version of the definition of a circular code would
allow $X=\left\{  \varnothing\right\}  $ (since the condition is vacuously
true: $s$ can never be nonempty if $\varnothing=ps$), and then the denominator
$1-f_{X}\left(  z\right)  $ in (1.3.16) would vanish.

\item \textbf{page 19:} On the line directly after (1.3.15), replace
\textquotedblleft in such a way that\textquotedblright\ by \textquotedblleft,
so that\textquotedblright. See, e.g.,
\href{http://scg.unibe.ch/wiki/howtos/commonwritingerrors/SuchThatVsSoThat}{this
page} about \textquotedblleft so that\textquotedblright\ vs. \textquotedblleft
such that\textquotedblright.

\item \textbf{page 19, Theorem 1.3.1:} \textquotedblleft let $S$ be the set of
words\textquotedblright\ $\rightarrow$ \textquotedblleft let $S$ be the set of
nonempty words\textquotedblright. It is not quite clear whether the empty word
counts as being conjugate to itself, but let's avoid this issue altogether by
forbidding it. (If you allowed the empty word to be in $S$, then the left hand
side of (1.3.17) would have constant term $1$ while the right hand side has
constant term $0$.)

\item \textbf{page 19, Theorem 1.3.1:} The period at the end of (1.3.16)
should be a comma.

\item \textbf{page 19, proof of Theorem 1.3.1:} \textquotedblleft is of this
form for some $x\in X$\textquotedblright\ $\rightarrow$ \textquotedblleft is
of this form for some unique $x\in X$\textquotedblright.

\item \textbf{page 19, proof of Theorem 1.3.1:} \textquotedblleft Thus
$g_{x,n}$\textquotedblright\ $\rightarrow$ \textquotedblleft Thus $g_{n,x}%
$\textquotedblright.

\item \textbf{page 19, proof of Theorem 1.3.1:} \textquotedblleft Formula
(1.3.16) is obtained from (1.3.17) by taking the derivative of the logarithm
of each side\textquotedblright\ $\rightarrow$ \textquotedblleft Formula
(1.3.16) is obtained from (1.3.17) by dividing both sides by $z$, then taking
antiderivatives (with constant term $0$) and exponentiating\textquotedblright.

\item \textbf{page 20:} \textquotedblleft in such a way that\textquotedblright%
\ $\rightarrow$ \textquotedblleft, so that\textquotedblright.

\item \textbf{page 20:} Between the first two paragraphs of this page, I would
add the following observation: The set $S$ is not a semigroup, but (due to
(1.3.15)) it is closed under taking powers and radicals (i.e., for a word
$w\in X^{\ast}$ and a positive integer $m$, we have $w\in S$ if and only if
$w^{m}\in S$). Furthermore, $S$ is closed under cyclic shifting, whence $S$ is
a disjoint union of necklaces.

\item \textbf{page 20:} Replace \textquotedblleft and let $p_{n}%
=\operatorname*{Card}\left(  P\cap A^{n}\right)  $\textquotedblright\ by
\textquotedblleft and let $p_{n}$ be the number of necklaces of length $n$
contained in $P$\textquotedblright. (The expression \textquotedblleft$P\cap
A^{n}$\textquotedblright\ is meaningless, since the elements of $P$ are
necklaces, not words.)

\item \textbf{page 20:} Add a period after \textquotedblleft Thus $c_{n}%
=\sum_{d\mid n}p_{d}$\textquotedblright.

\item \textbf{page 22, Proposition 7:} \textquotedblleft of its proper
suffixes\textquotedblright\ $\rightarrow$ \textquotedblleft of its nonempty
proper suffixes\textquotedblright.

\item \textbf{page 22, proof of Proposition 7:} After \textquotedblleft But
$uv<tv$ implies $u<t$\textquotedblright, add \textquotedblleft(because
$\left\vert u\right\vert =\left\vert w\right\vert -\left\vert v\right\vert
=\left\vert t\right\vert $)\textquotedblright.

\item \textbf{page 22, proof of Proposition 8:} Replace \textquotedblleft$m<v$
and thus $\ell m<m<v$\textquotedblright\ by \textquotedblleft$m\leq v$ and
thus $\ell m<m\leq v$\textquotedblright.

\item \textbf{page 22, proof of Proposition 8:} After \textquotedblleft we
have $v=v^{\prime}m$\textquotedblright, add \textquotedblleft for some
nonempty suffix $v^{\prime}$ of $\ell$\textquotedblright.

\item \textbf{page 22, proof of Proposition 8:} After \textquotedblleft Then
$\ell<v^{\prime}$\textquotedblright, add \textquotedblleft(but $\left\vert
\ell\right\vert >\left\vert v^{\prime}\right\vert $)\textquotedblright.

\item \textbf{page 23:} You write: \textquotedblleft It motivated Knuth to
call Lyndon words \textit{prime} words in [26]\textquotedblright. This is
correct, but it is worth mentioning that David Radford already called them
\textquotedblleft primes\textquotedblright\ in his 1977 paper \textit{A
Natural Ring Basis for the Shuffle Algebra and an Application to Group
Schemes} (Journal of Algebra \textbf{58} (1979), pp. 432--454), except that he
works with the reverse of the lexicographic order on $A^{\ast}$.

\item \textbf{page 23, proof of Lemma 1:} \textquotedblleft let $v$ be the
minimal suffix\textquotedblright\ $\rightarrow$ \textquotedblleft let $v$ be
the minimal nonempty suffix\textquotedblright.

\item \textbf{page 23, Proposition 9:} This proposition also easily follows
from Exercise 6.1.32 in
\href{https://arxiv.org/src/1409.8356v5/anc/HopfComb-v73-with-solutions.pdf}{Darij
Grinberg and Victor Reiner, \textit{Hopf Algebras in Combinatorics},
arXiv:1409.8356v5}. (Indeed, combining parts (c) and (b) of this exercise
yields the implication $\mathcal{F}^{\prime}\Longrightarrow\mathcal{G}%
^{\prime}$, which shows that each word in $P$ is a sesquipower of a Lyndon
word; conversely, if $w$ is a sesquipower of a Lyndon word distinct from the
maximal letter, then parts (f) and (b) of the exercise yield the relation
$\mathcal{G}^{\prime}\Longrightarrow\mathcal{F}^{\prime}$, which entails that
$w\in P$.)

I am mentioning this because the exercise gives a few more equivalent
characterizations of $P$.

\item \textbf{page 24, proof of Lemma 2:} After the first sentence of this
proof, add: \textquotedblleft Pick $n$ minimal with this
property\textquotedblright.

\item \textbf{page 24, proof of Lemma 2:} How exactly does $x<tar$ yield $q<t$
? Couldn't $t$ be a prefix of $q$ ?

I don't know the answer, but here is an alternative way of proving the claim
that you are actually trying to prove: We want to show that $qb\in L$. Assume
the contrary. Thus, according to the contrapositive of Proposition 7, there
exists some nonempty proper suffix of $qb$ that is not larger than $qb$.
Consider this suffix, and observe that it must have the form $tb$ for some
proper suffix $t$ of $q$ (since every nonempty proper suffix of $qb$ has this
form). Consider this $t$. Thus, $tb$ is not larger than $qb$. In other words,
$tb\leq qb$. But $t$ is a proper suffix of $q$, and thus $tar$ is a proper
suffix of $x$ (since $x=qar$). By Proposition 7, this implies that $x<tar$
(since $x$ is Lyndon). Thus, $qar=x<tar$. If $t$ is not a prefix of $q$, then
this yields $q<t$ and therefore $qb<tb$ (since $q$ is longer than $t$ and thus
cannot be a prefix of $t$), which contradicts $tb\leq qb$. Thus, $t$ must be a
prefix of $q$. In other words, $q=th$ for some word $h$. Consider this $h$.
This word $h$ is nonempty (since otherwise, we would have $h=\varnothing$ and
thus $q=t\underbrace{h}_{=\varnothing}=t$, which would contradict the fact
that $t$ is a proper suffix of $q$). We have $tb\leq qb=thb$ (since $q=th$),
thus $b\leq hb$. Hence, $b\leq h_{1}$, where $h_{1}$ denotes the first letter
of $h$. (Note that the first letter of $h$ exists, because $h$ is nonempty.)
Hence, $a<b\leq h_{1}$, so that $ar\leq h$ and therefore $tar\leq th=q\leq
qar$. This contradicts $qar<tar$. This contradiction shows that our assumption
was false. Hence, we have proven that $qb\in L$.

\item \textbf{page 24, proof of Lemma 2:} \textquotedblleft for any $m\geq
1$\textquotedblright\ $\rightarrow$ \textquotedblleft for any $m\geq
0$\textquotedblright\ (in the last sentence of this proof).

\item \textbf{page 24, proof of Proposition 9:} After \textquotedblleft we
have $x^{n}pb\in L$\textquotedblright, add \textquotedblleft(since $x^{n}pb$
is a prefix of the minimal word $x^{n}\underbrace{paq}_{=x}=x^{n+1}%
$)\textquotedblright.

\item \textbf{page 24, proof of Proposition 9:} \textquotedblleft then $w$ is
is\textquotedblright\ $\rightarrow$ \textquotedblleft then $w$
is\textquotedblright.

\item \textbf{page 24, proof of Proposition 9:} \textquotedblleft Finally if
$b<a$, $w$ is a Lyndon word by Lemma 2\textquotedblright\ $\rightarrow$
\textquotedblleft Finally, if $b<a$, then $w$ is a Lyndon word by Lemma 2
(applied to $v$, $b$ and $a$ instead of $p$, $a$ and $b$), because $vb$ is a
prefix of the minimal word $vbu=y^{n+1}$\textquotedblright.

\item \textbf{page 24, \S 1.4.2:} \textquotedblleft an
extension\textquotedblright\ $\rightarrow$ \textquotedblleft an $n$%
-extension\textquotedblright\ (you haven't defined the word \textquotedblleft
extension\textquotedblright\ on its own).

\item \textbf{page 26:} \textquotedblleft assignement\textquotedblright%
\ $\rightarrow$ \textquotedblleft assignment\textquotedblright.

\item \textbf{page 26, \S 1.5:} You use the word \textquotedblleft
graph\textquotedblright\ to mean \textquotedblleft directed
graph\textquotedblright. This should probably be explained.

\item \textbf{page 26, \S 1.5:} \textquotedblleft The de Bruijn graph of
orders\textquotedblright\ $\rightarrow$ \textquotedblleft The de Bruijn graphs
of orders\textquotedblright.

\item \textbf{page 26, \S 1.5:} Your notion of a \textquotedblleft
cycle\textquotedblright\ in a graph allows repeated vertices. This being
unusual, I suggest you clarify this explicitly. (Normally, this notion is
known as \textquotedblleft circuit\textquotedblright, not as \textquotedblleft
cycle\textquotedblright.)

The same applies to the notion of a \textquotedblleft path\textquotedblright%
\ (from page 28 onwards). (Your notion of \textquotedblleft
path\textquotedblright\ is normally called \textquotedblleft
walk\textquotedblright.)

\item \textbf{page 27, caption of Figure 1.5.7:} \textquotedblleft de
Bruin\textquotedblright\ $\rightarrow$ \textquotedblleft de
Bruijn\textquotedblright.

\item \textbf{page 27, proof of Theorem 1.5.1:} How do you know that
\textquotedblleft Every vertex of $H$ has an indegree equal to its
outdegree\textquotedblright? I understand why this would be true for weakly
connected components, but why for strictly connected components?

You can fix this problem by replacing \textquotedblleft strongly
connected\textquotedblright\ by \textquotedblleft weakly
connected\textquotedblright\ (i.e., cannot be written as a union of two
vertex-disjoint subgraphs) in Theorem 1.5.1 and throughout its proof.

\item \textbf{page 27, proof of Theorem 1.5.1:} \textquotedblleft Eulerian
cycle\textquotedblright\ $\rightarrow$ \textquotedblleft Euler
cycle\textquotedblright.

\item \textbf{page 28:} \textquotedblleft and by $d^{-}\left(  v\right)  $ its
outdegree\textquotedblright\ $\rightarrow$ \textquotedblleft and by
$d^{+}\left(  v\right)  $ its outdegree\textquotedblright.

\item \textbf{page 28:} \textquotedblleft A variant of an Euler cycle is that
of \textit{Euler path}\textquotedblright\ $\rightarrow$ \textquotedblleft A
variant of an Euler cycle is the notion of an \textit{Euler path}%
\textquotedblright.

\item \textbf{page 28:} \textquotedblleft that a graph\textquotedblright%
\ $\rightarrow$ \textquotedblleft that a strongly connected
graph\textquotedblright.

\item \textbf{page 28:} After \textquotedblleft has an Euler path from $x$ to
$y$\textquotedblright, add \textquotedblleft(where $x$ and $y$ are two given
distinct vertices)\textquotedblright.

\item \textbf{page 28 and further:} \textquotedblleft Eulerian
path\textquotedblright\ $\rightarrow$ \textquotedblleft Euler
path\textquotedblright\ (or vice versa, but consistently).

\item \textbf{page 28:} In the discussion of the \textsc{Euler} algorithm, it
appears that \textquotedblleft$p$\textquotedblright\ should be
\textquotedblleft$t$\textquotedblright.

\item \textbf{page 28, \S 1.5.1:} \textquotedblleft de Bruin\textquotedblright%
\ $\rightarrow$ \textquotedblleft de Bruijn\textquotedblright.

\item \textbf{page 28, \S 1.5.1:} In the definition of $\pi\left(  G\right)
$, you want $G$ to have at least one outgoing edge from each vertex (so that
the factors $\left(  d^{+}\left(  v\right)  -1\right)  !$ are well-defined).

\item \textbf{page 28 and elsewhere:} \textquotedblleft van
Aarden\textquotedblright\ $\rightarrow$ \textquotedblleft van
Aardenne\textquotedblright.

\item \textbf{page 29, Theorem 1.5.3:} Replace \textquotedblleft$t\left(
G\right)  $\textquotedblright\ by \textquotedblleft$t\left(  v\right)
$\textquotedblright\ both times in this theorem. (You use the
\textquotedblleft$t\left(  v\right)  $\textquotedblright\ notation later in
the proof, and it is the more reasonable notation, since this value depends on
$v$.)

\item \textbf{page 29, proof of Theorem 1.5.3:} Replace \textquotedblleft%
$\varphi$\textquotedblright\ by \textquotedblleft$\varphi_{v}$%
\textquotedblright\ (or vice versa) throughout the proof.

\item \textbf{page 29, proof of Theorem 1.5.3:} Your claim that
\textquotedblleft we reach $v$ in a finite number of steps\textquotedblright%
\ needs to be proven.

(The proof is not very difficult: If we start at $w$ and keep following
$T$-edges\footnote{A \textquotedblleft$T$\textit{-edge}\textquotedblright%
\ means an edge that belongs to $T$.} (let us call this the $T$\textit{-walk}%
), then the edges we traverse appear in our Euler path $P$ in the same order
as we traverse them in the $T$-walk (because otherwise, there would be a
subpath $p\overset{a}{\longrightarrow}q\overset{b}{\longrightarrow}r$ of our
$T$-walk consisting entirely of $T$-edges such that $a$ appears later than $b$
in the Euler path $P$; but this would mean that after traversing $a$, the
Euler path $P$ gets stuck at the vertex $q$ because it has already traversed
the last outgoing edge from $q$ (namely, $b$); but this is clearly absurd
since $q\neq v$). Hence, we cannot keep following these edges forever; i.e.,
our $T$-walk must end at some vertex. This vertex clearly must be $v$, since
$v$ is the only vertex without an outgoing $T$-edge. And so we reach $v$ in a
finite number of steps.)

\item \textbf{page 29, proof of Theorem 1.5.3:} Your claim that
\textquotedblleft There results an Euler path $P$ from $v$ to $v$ which is
such that $\varphi\left(  P\right)  =T$\textquotedblright. This needs to be proven.

(Here is how I prove this:

First, let us show that for every vertex $w\neq v$, there exists exactly one
$T$-edge outgoing from $w$. Indeed, such a $T$-edge clearly exists (since $T$
is a spanning tree oriented towards $v$, and therefore each vertex has a path
to $v$). But if there were two distinct $T$-edges outgoing from the same
vertex $w$, then they could be extended to two different $T$-paths\footnote{A
\textquotedblleft$T$\textit{-path}\textquotedblright\ means a path that uses
only edges from $T$.} from $w$ to $v$ (since $T$ is a spanning tree oriented
towards $v$, and therefore each vertex has a path to $v$); but the definition
of a \textquotedblleft spanning tree oriented towards $v$\textquotedblright%
\ shows that there can be only one such a $T$-path. Hence, for every vertex
$w\neq v$, there exists exactly one $T$-edge outgoing from $w$. This shows
that (for a vertex $w\neq v$) we can speak of \textquotedblleft the $T$-edge
outgoing from $v$\textquotedblright\ (without having to check that it exists
and is unique).

For a similar reason, there cannot be any $T$-edge outgoing from $v$ (indeed,
such a $T$-edge would start a nontrivial $T$-path from $v$ to $v$, but there
is also a trivial $T$-path from $v$ to $v$, and having two different $T$-paths
from $v$ to $v$ would cause the same contradiction as before).

The path $P$ that we build must end at some vertex $w$ (since eventually we
run out of unused edges). Consider this $w$.

Let us first show that $w=v$. Indeed, assume the contrary. Then, the path $P$
has entered $w$ more often than it has exited $w$; but this means that there
is still at least one outgoing edge from $w$ left unused (because
$d^{+}\left(  w\right)  =d^{-}\left(  w\right)  $ (since $G$ is Eulerian)).
This is absurd, because the path $P$ can only get stuck at a vertex if all
outgoing edges from this vertex have been used. This contradiction shows that
our assumption was false. Hence, $w=v$ is proven. Thus, $P$ is a path from $v$
to $v$. Hence, $P$ is a closed path.

Next, we need to show that the path $P$ is an Euler path. Indeed, assume the
contrary. Thus, the path $P$ leaves at least one edge of $G$ unused.

Fix a vertex $w$ of $G$. Then,%
\begin{align*}
&  \left(  \text{the number of outgoing edges from }w\text{ unused by
}P\right) \\
&  =\underbrace{\left(  \text{the number of outgoing edges from }w\right)
}_{\substack{=d^{+}\left(  w\right)  =d^{-}\left(  w\right)  \\\text{(since
}G\text{ is Eulerian)}}}\\
&  \ \ \ \ \ \ \ \ \ \ -\underbrace{\left(  \text{the number of outgoing edges
from }w\text{ used by }P\right)  }_{\substack{=\left(  \text{the number of
incoming edges into }w\text{ used by }P\right)  \\\text{(since }P\text{ is a
closed walk, and thus leaves }w\text{ as often as it enters }w\text{)}}}\\
&  =\underbrace{d^{-}\left(  w\right)  }_{=\left(  \text{the number of
incoming edges into }w\right)  }\\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the number of incoming edges into
}w\text{ used by }P\right) \\
&  =\left(  \text{the number of incoming edges into }w\right) \\
&  \ \ \ \ \ \ \ \ \ \ -\left(  \text{the number of incoming edges into
}w\text{ used by }P\right) \\
&  =\left(  \text{the number of incoming edges into }w\text{ unused by
}P\right)  .
\end{align*}
Hence, there exists an outgoing edge from $w$ unused by $P$ if and only if
there exists an incoming edge into $w$ unused by $P$. In this case, we shall
say that the vertex $v$ is \textit{unfulfilled} (by the path $P$).

Forget that we fixed $w$. We thus have defined the notion of an
\textquotedblleft unfulfilled\textquotedblright\ vertex. At least one vertex
of $G$ is unfulfilled (since the path $P$ leaves at least one edge of $G$ unused).

Next, we shall argue that%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\text{if }p\text{ is an unfulfilled vertex, and if }q\text{ is any vertex}\\
\text{such that there exists a }T\text{-edge from }p\text{ to }q\text{,}\\
\text{then }q\text{ is unfulfilled as well}%
\end{array}
\right)  . \label{p29.5}%
\end{equation}


[\textit{Proof of (\ref{p29.5}):} Let $p$ be an unfulfilled vertex. Let $q$ be
any vertex such that there exists a $T$-edge from $p$ to $q$. We must show
that $q$ is unfulfilled as well.

The vertex $p$ is unfulfilled. In other words, there exists an outgoing edge
from $p$ unused by $P$ (by the definition of \textquotedblleft
unfulfilled\textquotedblright). Hence, the $T$-edge outgoing from $p$ is also
left unused by $P$ (since $P$ only uses $T$-edges as a last resort, once all
the other outgoing edges are used up). This $T$-edge must be precisely the
$T$-edge from $p$ to $q$ whose existence we have assumed (because there is
only one $T$-edge outgoing from $p$). Hence, this $T$-edge is incoming into
$q$. Thus, there exists an incoming edge into $q$ unused by $P$. In other
words, $q$ is unfulfilled (by the definition of \textquotedblleft
unfulfilled\textquotedblright). This proves (\ref{p29.5}).]

Recall that a $T$-path consists of $T$-edges. Hence, the following holds:%
\begin{equation}
\left(
\begin{array}
[c]{c}%
\text{if }p\text{ is an unfulfilled vertex, and if }q\text{ is any vertex}\\
\text{such that there exists a }T\text{-path from }p\text{ to }q\text{,}\\
\text{then }q\text{ is unfulfilled as well}%
\end{array}
\right)  . \label{p29.6}%
\end{equation}
(Indeed, this can be proven by induction on the length of the $T$-path, using
(\ref{p29.5}) in the induction step.)

Now, recall that at least one vertex of $G$ is unfulfilled. Pick such a vertex
and denote it by $p$. There exists a $T$-path from $p$ to $v$ (since $T$ is a
spanning tree oriented towards $v$). Hence, (\ref{p29.6}) (applied to $q=v$)
shows that $v$ is unfulfilled. In other words, there exists an outgoing edge
from $v$ unused by $P$ (by the definition of \textquotedblleft
unfulfilled\textquotedblright). But this contradicts the fact that the path
$P$ ends at $v$ (since the path $P$ only ends when it arrives at a vertex
whose all outgoing edges are already used). This contradiction shows that our
assumption was false. Hence, $P$ is an Euler path.)

\item \textbf{page 29, proof of Theorem 1.5.3:} \textquotedblleft$\pi\left(
v\right)  $\textquotedblright\ should be \textquotedblleft$\pi\left(
G\right)  $\textquotedblright\ at the very end of this proof.

\item \textbf{page 30:} \textquotedblleft Let $M$ be its adjacency matrix
defined\textquotedblright\ $\rightarrow$ \textquotedblleft Let $M$ be its
adjacency matrix, i.e., the $V\times V$-matrix defined\textquotedblright.

\item \textbf{page 30:} \textquotedblleft Let $D$ be the diagonal
matrix\textquotedblright\ $\rightarrow$ \textquotedblleft Let $D$ be the
diagonal $V\times V$-matrix\textquotedblright.

\item \textbf{page 30, Theorem 1.5.4:} Add a period at the end of this theorem.

\item \textbf{page 30, proof of Theorem 1.5.4:} The induction base (i.e., the
case when there are no edges) needs a separate treatment of the case when
$V=\left\{  v\right\}  $ (because if $V=\left\{  v\right\}  $, then
$N_{v}\left(  G\right)  $ and $K_{v}\left(  G\right)  $ are $1$, not $0$).

\item \textbf{page 30, proof of Theorem 1.5.4:} The induction step does not
work when $w=v$ (that is, when $e$ is a self-loop). Such edges can be dealt
with through a much simpler argument, of course (just observe that neither
$N_{v}\left(  G\right)  $ nor $K_{v}\left(  G\right)  $ changes when a
self-loop is removed); but this should be mentioned.

\item \textbf{page 30, proof of Theorem 1.5.4:} \textquotedblleft and
$G^{\prime\prime}$ the graph obtained by merging $v$ and $w$\textquotedblright%
\ $\rightarrow$ \textquotedblleft and $G^{\prime\prime}$ the graph obtained
from $G^{\prime}$ by merging $v$ and $w$\textquotedblright.

I would also explicitly say that all other edges between $v$ and $w$ (apart
from $e$) become self-loops when $v$ and $w$ are merged.

\item \textbf{page 31, proof of Theorem 1.5.4:} \textquotedblleft being the
same\textquotedblright\ $\rightarrow$ \textquotedblleft is the
same\textquotedblright.

\item \textbf{page 31, proof of Theorem 1.5.4:} Before \textquotedblleft By
(1.5.22) and (1.5.23)\textquotedblright, add a period.

\item \textbf{page 31, Example 13:} You should probably say that in
constructing the matrix $L$, you have chosen the vertices $bb,ba,ab,aa$ of $G$
to correspond to the rows $1,2,3,4$ (and the columns $1,2,3,4$) of the matrix
$L$ in this order.

\item \textbf{page 31, Example 13:} Add a period after the displayed equation,
and remove the period just before the displayed equation.

\item \textbf{page 31, Example 13:} \textquotedblleft by Example
1.5.8\textquotedblright\ $\rightarrow$ \textquotedblleft by Example
12\textquotedblright.

\item \textbf{page 31:} You should say that \textquotedblleft the de Bruijn
graph $G_{n}$\textquotedblright\ means the de Bruijn graph of order $n$ on the
$k$-letter alphabet $A$.

\item \textbf{page 31:} The sentence \textquotedblleft If $G$ is regular, the
number $t\left(  G\right)  $ of spanning trees oriented towards a vertex $v$
does not depend on $v$\textquotedblright\ is confusing (this has to do with
the Eulerianness, not with the regularity, of $G$). I suggest replacing it by
the following:

\textquotedblleft If $G$ is Eulerian, then the number $t\left(  v\right)  $ of
spanning trees oriented towards a vertex $v$ does not depend on $v$ (since
Theorem 1.5.3 shows that it equals the number of Euler cycles of $G$ divided
by $\pi\left(  G\right)  $). Thus, we can denote this number by $t\left(
G\right)  $. Hence, in particular, $t\left(  G\right)  $ is defined whenever
$G$ is a regular graph (since any regular graph is
Eulerian).\textquotedblright

\item \textbf{page 31, Theorem 1.5.5:} An alternative (combinatorial) proof of
this theorem (and actually of a more general result) has been given in: Hoda
Bidkhori, Shaunak Kishore, \textit{A Bijective Proof of a Theorem of Knuth},
Combinatorics, Probability and Computing \textbf{20} (2011), Issue 01, pp.
11--25, Theorem 1.1.

\item \textbf{page 32, Lemma 3:} \textquotedblleft its longest
prefix\textquotedblright\ $\rightarrow$ \textquotedblleft the longest prefix
of $w$\textquotedblright. (There are two different words to which the
\textquotedblleft its\textquotedblright\ could refer to.)

\item \textbf{page 32, proof of Lemma 3:} You say that \textquotedblleft%
$wv<sv$\textquotedblright. This is only true if $s\neq\varnothing$. (Of
course, the case when $s=\varnothing$ is easy to deal with, but not in the
exact way you are doing it.)

\item \textbf{page 32, proof of Lemma 3:} I don't understand this proof
(starting with the \textquotedblleft If $t\leq n-r$\textquotedblright\ part).
Here is, instead, how I would prove Lemma 3 (not claiming that this is a
better proof):

\textit{Alternative proof of Lemma 3.} The word $w$ belongs to the set $P$
that was defined in \S 1.4.1 (since it is a prefix of a Lyndon word). Hence,
it is a sesquipower of a Lyndon word (by Proposition 9). In other words, there
exists a Lyndon word $v$ such that $w$ is a sesquipower of $v$. We shall prove
that $v=\ell$.

Indeed, $w$ is a sesquipower of $v$. In other words, there exist $n\geq1$ and
a proper prefix $p$ of $v$ such that $w=v^{n}p$. Consider these $n$ and $p$.
Theorem 1.4.1 shows that the word $p$ factorizes uniquely as a nonincreasing
product of Lyndon words. In other words, there exist unique Lyndon words
$p_{1},p_{2},\ldots,p_{k}$ such that $p_{1}\geq p_{2}\geq\cdots\geq p_{k}$ and
$p=p_{1}p_{2}\cdots p_{k}$. Consider these $p_{1}p_{2}\cdots p_{k}$. We have
$w=\underbrace{v^{n}}_{=\underbrace{vv\cdots v}_{n\text{ times}}%
}\underbrace{p}_{=p_{1}p_{2}\cdots p_{k}}=\underbrace{vv\cdots v}_{n\text{
times}}p_{1}p_{2}\cdots p_{k}$. But the sequence $\underbrace{v,v,\ldots
,v}_{n\text{ times}},p_{1},p_{2},\ldots,p_{k}$ of Lyndon words is
nonincreasing\footnote{\textit{Proof.} In order to see this, we need to check
that $v\geq v\geq\cdots\geq v\geq p_{1}\geq p_{2}\geq\cdots\geq p_{k}$. If
$k=0$, then this is obvious, so let us WLOG assume that $k\neq0$. Hence,
$p_{1}$ exists.
\par
We have $p_{1}\leq p_{1}p_{2}\cdots p_{k}=p\leq v$ (since $p$ is a prefix of
$v$), so that $v\geq p_{1}$. Combining this with $p_{1}\geq p_{2}\geq
\cdots\geq p_{k}$, we find $v\geq p_{1}\geq p_{2}\geq\cdots\geq p_{k}$, so
that $v\geq v\geq\cdots\geq v\geq p_{1}\geq p_{2}\geq\cdots\geq p_{k}$. Qed.}.
Hence, we can apply Lemma 1 to this sequence instead of $\ell_{1},\ldots
,\ell_{m}$ (since $w=\underbrace{vv\cdots v}_{n\text{ times}}p_{1}p_{2}\cdots
p_{k}$). We thus conclude that $v$ is the longest prefix of $w$ which is a
Lyndon word (and that the last word in this sequence is the minimal nonempty
suffix of $w$; but this is not something we need to know). In other words, $v$
is the longest prefix of $w$ in $L$. But $\ell$, too, is the longest prefix of
$w$ in $L$. Thus, both $v$ and $\ell$ are defined in the same way. Hence,
$v=\ell$. Now, $w$ is a sesquipower of $v$. In other words, $w$ is a
sesquipower of $\ell$ (since $v=\ell$). Hence, $w$ is the $n$-extension of
$\ell$ (since $w$ has length $\ell$). This proves Lemma 3. $\blacksquare$

\item \textbf{page 32, proof of Theorem 1.5.6:} You are using the notation
$\lambda^{\ast}$ for the Kleene closure $\left\{  \lambda\right\}  ^{\ast}$
where $\lambda$ is a single letter. This is worth saying.

\item \textbf{page 32, proof of Theorem 1.5.6:} It is somewhat confusing to
declare $u$ and $v$ separately in each of the three cases (a), (b) and (c). I
would find it better to introduce them globally, as follows: The word $w$ can
clearly be written as $w=r^{d}$ for some primitive word $r$ and some positive
integer $d$. Consider these $r$ and $d$. Write $r$ as $r=uv$ in such a way
that $vu\in L$ (this can be done, since every primitive word has exactly one
Lyndon word in its necklace). Thus, $vu=\ell_{k}$ for some $k$ (although you
don't seem to call it $k$ in case (b)). Now, the three cases are simply:

(a) the case when $d=1$ and $u\notin z^{\ast}$;

(b) the case when $d=1$ and $u\in z^{\ast}$;

(c) the case when $d>1$.

[Note: I still don't understand this proof, so I am not completely sure that
this change is the right thing to do.]

\item \textbf{page 34:} You write: \textquotedblleft we denote by $X_{s}$ the
set of words such that no factor has a conjugate in $\left\{  \ell_{1}%
,\ldots,\ell_{s}\right\}  $\textquotedblright. This seems to be a wrong
definition of $X_{s}$, as it would imply that (for $s\geq1$) the words in
$X_{s}$ cannot contain the letter $a$ (since such a letter would be a factor
conjugate to $a=\ell_{1}$). Or are you talking of factors in the factorization
of Theorem 1.4.1? (Even in this case, I guess you mean \textquotedblleft
conjugate in $\left\{  \ell_{1},\ldots,\ell_{s-1}\right\}  $\textquotedblright%
\ rather than \textquotedblleft conjugate in $\left\{  \ell_{1},\ldots
,\ell_{s}\right\}  $\textquotedblright, though. I don't know for sure since I
haven't read Moreno's paper.)

\item \textbf{page 34 and further:} \textquotedblleft$\left(  a_{n}\right)
_{n\in Z}$\textquotedblright\ should be \textquotedblleft$\left(
a_{n}\right)  _{n\in\mathbb{Z}}$\textquotedblright.

\item \textbf{page 34, \S 1.6:} \textquotedblleft It is of course equivalent
to ask\textquotedblright: Why?

\item \textbf{page 35, proof of Proposition 11 and further:} \textquotedblleft%
$\left(  a_{n}\right)  _{n\in\mathcal{Z}}$\textquotedblright\ should be
\textquotedblleft$\left(  a_{n}\right)  _{n\in\mathbb{Z}}$\textquotedblright.

\item \textbf{page 36, Figure 1.6.9:} This figure collides with the header of
the page.

\item \textbf{page 39, Theorem 1.6.2:} Here you seem to be repeating the last
paragraph before Example 18 from page 38.

\item \textbf{page 39, Proposition 16:} \textquotedblleft a proper suffix of
$m$\textquotedblright\ $\rightarrow$ \textquotedblleft a proper nonempty
suffix of $m$\textquotedblright.

\item \textbf{page 39, proof of Proposition 16:} \textquotedblleft Let $t$ be
a proper suffix\textquotedblright\ $\rightarrow$ \textquotedblleft Let $t$ be
a proper nonempty suffix\textquotedblright.

\item \textbf{page 39, proof of Proposition 16:} In Case 1, replace
\textquotedblleft$\ell^{n}s$\textquotedblright\ by \textquotedblleft$\ell
^{i}s$\textquotedblright.

\item \textbf{page 39, proof of Proposition 16:} In Case 2, why do we have
\textquotedblleft$t>\ell^{i}s$\textquotedblright?

\item \textbf{page 39, proof of Proposition 16:} In Case 3, replace
\textquotedblleft proper suffix\textquotedblright\ by \textquotedblleft proper
nonempty suffix\textquotedblright.

\item \textbf{page 42, \S 1.6:} \textquotedblleft are build in this
way\textquotedblright\ $\rightarrow$ \textquotedblleft are built in this
way\textquotedblright.

\item \textbf{page 42, \S 1.7:} \textquotedblleft Suppose $w$
is\textquotedblright\ $\rightarrow$ \textquotedblleft Suppose $w=a_{1}%
a_{2}\cdots a_{n}$ is\textquotedblright. (You later use the notation $a_{i}$
for the letters of $w$.)

\item \textbf{page 43, (1.7.25):} Add a period at the end of this equality.

\item \textbf{page 43, (1.7.26):} Add a period at the end of this equality.

\item \textbf{page 43:} \textquotedblleft Indeed, $b_{\sigma\left(  i\right)
}$ is the last letter of $w_{\sigma\left(  i\right)  }$\textquotedblright%
\ $\rightarrow$ \textquotedblleft Indeed, $b_{\sigma\left(  j\right)  }$ is
the last letter of $w_{\sigma\left(  j\right)  }$\textquotedblright.

\item \textbf{page 43:} Remove the indentation after (1.7.28).

\item \textbf{page 44, Remark 1.7.1:} Replace \textquotedblleft$\sigma\left(
i\right)  =\pi^{i-1}\left(  1\right)  $\textquotedblright\ by
\textquotedblleft$\sigma\left(  i\right)  =\pi^{i-1}\left(  \sigma\left(
1\right)  \right)  $\textquotedblright.

\item \textbf{page 47:} When you speak of \textquotedblleft the order
$\curlyeqprec_{\omega}$\textquotedblright, it is worth pointing out that it is
a (total) pre-order, not a (total) order. Indeed, if two words $u$ and $v$ are
powers of one and the same word, then $u\curlyeqprec_{\omega}v$ and
$v\curlyeqprec_{\omega}u$.

\item \textbf{page 47:} \textquotedblleft multiset of
necklaces\textquotedblright\ $\rightarrow$ \textquotedblleft multiset of
primitive necklaces\textquotedblright.

\item \textbf{page 47:} \textquotedblleft$u^{L\setminus\left\vert u\right\vert
}$\textquotedblright\ $\rightarrow$ \textquotedblleft$u^{L/\left\vert
u\right\vert }$\textquotedblright.

\item \textbf{page 48, Theorem 1.8.1:} Have you really shown that $\Phi$ is a
bijection? I see at most a proof of the injectivity of $\Phi$ here.

\item \textbf{page 55, Theorem 1.9.4:} Add a period at the end of this equation.

\item \textbf{page 56:} \textquotedblleft By Lemma4\textquotedblright%
\ $\rightarrow$ \textquotedblleft By Lemma 4\textquotedblright.
\end{itemize}


\end{document}