\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{pstricks}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\usepackage{enumerate}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\theoremstyle{plain}
\newtheorem{question}[theorem]{Question}

\begin{center}
\vskip 1cm
{\LARGE\bf Do the Properties of an $S$-adic Representation
\vskip .10in
 Determine Factor Complexity?}
%\vskip 0.5cm
%{\bf (Towards a Statement of the $S$-adic
%Conjecture through Examples)}
\vskip 1cm
\small Fabien Durand\\
LAMFA, CNRS UMR 7352\\
Universit\'e de Picardie Jules Verne\\
UFR des Sciences\\
33, rue Saint-Leu\\
80039 Amiens Cedex 1 \\
France\\
\href{mailto:fabien.durand@u-picardie.fr}{\tt fabien.durand@u-picardie.fr}\\
\ \\
Julien Leroy\\
Department of Mathematics\\
University of Li\`ege\\
Grande Traverse 12 (B37)\\
B-4000 Li\`ege, Belgium\\
and\\
LAMFA, CNRS UMR 7352\\
Universit\'e de Picardie Jules Verne\\
UFR des Sciences\\
33, rue Saint-Leu\\
80039 Amiens Cedex 1 \\
France\\
\href{mailto:julien.leroy@uni.lu}{\tt julien.leroy@uni.lu} \\
\ \\
Gwena\"el Richomme\\
Universit\'e Paul-Val\'ery Montpellier 3\\
UFR IV, Dpt MIAp, Case J11\\
Route de Mende\\
34199 Montpellier Cedex 5 \\
France\\
and\\
LIRMM (CNRS, Univ. Montpellier 2) - UMR 5506 - CC 477\\
161 rue Ada \\
34095 Montpellier Cedex 5 \\
France\\
\href{mailto:gwenael.richomme@lirmm.fr}{\tt gwenael.richomme@lirmm.fr}\\
\end{center}

\vskip .2 in
\begin{abstract}
The $S$-adic conjecture postulates the existence of a
condition $C$ such that a sequence has linear complexity if and only if it is an $S$-adic sequence satisfying $C$ for some finite set $S$ of morphisms. 
We present an overview of the factor complexity of $S$-adic sequences and we give some examples that either illustrate some interesting properties,
or that are counterexamples to what might seem to be a ``good'' condition $C$. 
\end{abstract}

\section{Introduction}

A common tool in the study of a sequence (or an infinite word)
$\mathbf{w}$ over a finite alphabet $A$ is the complexity function
$p_\mathbf{w}$ (or simply $p$) that counts the number of factors of
each length $n$ occurring in the sequence, i.e., $p_{\mathbf{w}}(n) =
{\rm Card}(\{u \in A^* \mid |u|=n \ \text{and}\ \exists x \in A^*,
\mathbf{y} \in A^{\mathbb{N}}: \mathbf{w} = xu\mathbf{y}\})$ (see
\cite[Chap.\ 4]{CANT} for a survey on complexity function). The set of
factors of length $n$ of $\mathbf{w}$ is denoted by ${\rm
Fac}_n(\mathbf{w})$ and ${\rm Fac}(\mathbf{w}) = \bigcup_{n \in
\mathbb{N}} {\rm Fac}_n(\mathbf{w})$. The complexity function
$p_{\mathbf{w}}$ is clearly bounded by $({\rm Card}(A))^n, n \in
\mathbb{N}$, but not every function can be a complexity function. As an
example, it is well known (see~\cite{Morse-Hedlund2}) that either the
sequence is ultimately periodic (and then $p_\mathbf{w}(n)$ is
ultimately constant), or its complexity function grows at least like
$n+1$. Non-periodic sequences with minimal complexity $p_\mathbf{w}(n)
= n+1$ for all $n$ exist. They are called \textit{Sturmian sequences}
and a large literature is devoted to them (see
\cite[Chap.\ 2]{Lothaire} and \cite[Chap.\ 6]{Pytheas-Fogg} for surveys
on these sequences).

There is a huge literature about sequences with low complexity.
Indeed, such sequences occur, for instance, in
combinatorics~\cite{allouche_survey,Cassaigne_big_thm,Cassaigne_resume,Glen-Justin,koskas,Rote},
dynamical
systems~\cite{Arnoux-Rauzy,Boshernitzan84,Boshernitzan92,chacon,ferenczi_survey},
number
theory~\cite{Adamczewski,Adamczewski2,AlloucheZamboni98,FerencziMauduit97},
and geometry~\cite{CanteriniSiegel01,HoltonZamboni98,Rauzy82}.  
In this paper, by ``linear complexity'' we mean that the number of
factors of length $n$ is $O(n)$, and
by ``low
complexity'' we usually mean linear complexity.

Moreover, many well-known families of sequences can
also be indefinitely desubstituted with a finite number of morphisms.
Formally, an \textit{$S$-adic sequence} is defined as follows. Let
$\mathbf{w}$ be a sequence over a finite alphabet $A$. If $S$ is a set
of morphisms (possibly infinite), an \textit{$S$-adic representation}
of $\mathbf{w}$ is given by a sequence $(\sigma_n: A_{n+1}^*
\rightarrow A_n^*)_{n \in \mathbb{N}}$ of morphisms in $S$ and a
sequence $(a_n)_{n \in \mathbb{N}}$ of letters, $a_i \in A_i$ for all
$i$, such that\footnote{{The topology over $A^{\mathbb{N}}$ is the
classical product topology of the discrete topology over $A$.}} $A_0 =
A$, $\mathbf{w} = \lim_{n \rightarrow +\infty} \sigma_0 \sigma_1 \cdots
\sigma_n (a_{n+1}^{\omega})$ {and $\lim_{n \rightarrow +\infty}
|\sigma_0 \sigma_1 \cdots \sigma_n (a_{n+1})|=+\infty$, where
$a_{n+1}^{\omega}$ is the sequence only composed of occurrences of
$a_{n+1}$}.  The sequence $(\sigma_n)_{n \in \mathbb{N}} \in
S^{\mathbb{N}}$ is the \textit{directive word} of the representation.
In the sequel, we will say that a sequence $\mathbf{w}$ is
\textit{$S$-adic} if there exists a set $S$ of morphisms such that
$\mathbf{w}$ admits an $S$-adic representation.

The notion of $S$-adicity first appeared when Ferenczi~\cite{Ferenczi}
proved that the set of factors of any uniformly recurrent sequence with
linear complexity admits an $S$-adic representation, with $S$
finite, satisfying $\lim_{n \to +\infty} \min_a \in A_{n+1} |\sigma_0
\sigma_1 \cdots \sigma_n(a)|=+\infty$. The present work found its
motivation in that paper. Indeed, an open problem is to determine the
link between being an $S$-adic sequence and having linear
complexity (see~\cite{Arnoux-Rauzy,Ferenczi,Leroy}). This problem is
called the \textit{$S$-adic conjecture}:

\begin{conjecture}[$S$-adic conjecture]
There exists a condition $C$ such that a sequence has 
linear complexity if and only if it is an $S$-adic sequence
satisfying Condition $C$ for some finite set $S$ of morphisms.
\end{conjecture} 

It is clear that we cannot avoid considering a
particular condition since there exist some pure substitutive
sequences with quadratic complexity.

In this paper, we present an overview of the factor complexity (aka
``subword complexity'') of
$S$-adic sequences and we give some examples that either illustrate
some interesting properties, or that are counterexamples to what might seem
to be a ``good'' condition $C$.

In what follows, we consider that alphabets are finite subsets of
$\mathbb{N}$ and if $\sigma: A^* \to B^*$ is a morphism with $A =
\{0,1,\dots,k\}$, we write $\sigma = [\sigma(0), \dots,\sigma(k)]$. The
following example is classical when considering $S$-adic sequences.

\begin{example}
\label{ex: sturmian}
Let us define the four morphisms $R_0$, $R_1$, $L_0$ and $L_1$ over $\{0,1\}$ by $R_0 = [0,10]$, $R_1 = [01,1]$, $L_0 = [0,01]$ and $L_1 = [10,1]$. Since the work of Morse and Hedlund~\cite{Morse-Hedlund}, it is well known that for any Sturmian sequence $\mathbf{w}$, there is a sequence $(k_n)_{n \in \mathbb{N}}$ of integers such that
\begin{equation}
\label{eq: sturmian}
	\mathbf{w} = \lim_{n \to +\infty} L_0^{k_0} R_0^{k_1} L_1^{k_2} R_1^{k_3} L_0^{k_4} R_0^{k_5} \cdots L_1^{k_{4n+2}} R_1^{k_{4n+3}} (0^{\omega}).
\end{equation}
With, for all $n \geq 1$, the additional assumptions ``$k_{2n}+k_{2n+1} \geq 1$'' and ``if $k_{2n} = 0$, then $k_{2n-1} \neq 0$'', the sequence $(k_n)_{n \in \mathbb{N}}$ is unique \cite{BHZ,LR07}.
\end{example}

It is important to notice that, when we talk about an $S$-adic
sequence, the corresponding directive word $(\sigma_n)_{n \in
\mathbb{N}} \in S^{\mathbb{N}}$ is always implicit (even when it is not
unique). Indeed, for a given set $S$ of morphisms, we will see that two
distinct $S$-adic sequences can have different properties depending on
their respective directive words.

Observe that another classical tool to study sequences is 
topological entropy ($h = \limsup_{n \to +\infty} \frac{\log(p(n))}{n}
$), also used in dynamical systems. However, as we are interested in
very low complexity (subexponential) sequences, it is of no help.

The paper is organized as follows. Section~\ref{section: comparaison}
aims to present an overview of the complexity functions of morphic and
$S$-adic sequences. Section~\ref{section: s-adicity and linear}
explores some necessary and some sufficient conditions on
directive words that might lead to a correct statement of the $S$-adic
conjecture. These conditions are illustrated through examples and
counterexamples and expressed in terms of growth rate, return words,
and composition rules of the morphisms and repetitions. A key tool to
prove or disprove
the linearity of the complexity of many examples is
the deep result of Cassaigne characterizing the linearity of the
complexity in terms of special factors (Theorem~\ref{theorem: cassaigne
diff de complexite} on page~\pageref{theorem: cassaigne diff de
complexite}). Section~\ref{section beyond lin} goes further than the
$S$-adic conjecture and proposes a new problem about the possible
complexities of everywhere-growing $S$-adic sequences.


\section{Comparison between morphic and $S$-adic sequences}
\label{section: comparaison}

The aim of this section is to compare morphic sequences with $S$-adic
sequences. In particular, we show that the factor complexity of morphic
sequences is rather restricted and can depend on 
combinatorial criteria, although this is not the case for $S$-adic
sequences.

\subsection{Morphic and pure morphic sequences}

\textit{Purely morphic sequences} correspond to $S$-adic sequences with ${\rm Card}(S)=1$. If $S=\{\sigma\}$, we then have $\sigma_0 \sigma_1 \sigma_2 \cdots = \sigma \sigma \sigma \cdots = \sigma^{\omega}$. In that case, the complexity functions that can occur were completely determined by Pansiot in~\cite{Pansiot}. Indeed, he proved that for pure morphic sequences $\mathbf{w} = \sigma^{\omega}(a) = \lim_{n \to +\infty} \sigma^n(a^{\omega})$ with $\sigma$ \textit{non-erasing} (i.e., $\sigma(b)$ is not the empty word for all letters $b$), the complexity function $p_{\mathbf{w}}(n)$ can have only five asymptotic behaviors that are\footnote{$f(n) \in \Theta(g(n))$ if $\exists C_1, C_2 >0, n_0 \ \forall n \geq n_0 \ |C_1 g(n)| \leq |f(n)| \leq |C_2 g(n)|$.} $\Theta(1)$, $\Theta(n)$, $\Theta(n \log n)$, $\Theta(n \log \log n)$ and $\Theta(n^2)$. Moreover, when the sequence $\mathbf{w}$ is aperiodic, Morse and Hedlund proved that its complexity function cannot be $\Theta(1)$ (see~\cite{Morse-Hedlund2}). Pansiot proved that the class of complexity of the sequence only depends on the growth rate of the length of the images.

\begin{definition}
\label{def: quasi-uniforme, poly div, expo div}
Recall that a morphism $\sigma: A^* \to A^*$ is said to be \textit{everywhere-growing} if it does not admit \textit{bounded letter}, i.e., letter $b$ such that $\lim_{n \to +\infty}|\sigma^n(b)|<+\infty$. We let $A_{\mathfrak{B},\sigma}$ (or $A_{\mathfrak{B}}$ when no confusion is possible) denote the set of bounded letters of $\sigma$. By opposition, a non-bounded letter is called a \textit{growing} letter. Since for all letters $a$, we have $|\sigma^n(a)| \in \Theta(n^{\alpha_a} \beta_a^n)$ for some $\alpha_a$ in $\mathbb{N}$ and $\beta_a \geq 1$ (see~\cite{L_system}), any everywhere-growing morphism satisfies exactly one of the following three definitions:
\begin{enumerate} 
	\item	a morphism $\sigma: A^* \to A^*$ is \textit{quasi-uniform} if there exists $\beta \geq 1$ such that for all letters $a \in A$, $|\sigma^n(a)| \in \Theta(\beta^n)$;
	
	\item	a morphism $\sigma: A^* \to A^*$ is \textit{polynomially diverging} if there exists $\beta >1$ and a function $\alpha: A \to \mathbb{N}$, $\alpha \neq 0$, such that for all letters $a \in A$, $|\sigma^n(a)| \in \Theta(n^{\alpha(a)} \beta^n)$;
	
	\item 	a morphism $\sigma: A^* \to A^*$ is \textit{exponentially diverging} if there exist $a_1,a_2 \in A$, $\alpha_1,\alpha_2 \in \mathbb{N}$ and $\beta_1,\beta_2 >1$ with $\beta_1 \neq \beta_2$ such that for each $i \in \{1,2\}$, $|\sigma^n(a_i)| \in \Theta(n^{\alpha_i} \beta_i^n)$.
\end{enumerate}
\end{definition}

\begin{theorem}[Pansiot~\cite{Pansiot}]
\label{thm: pansiot}
Let $\mathbf{w} = \sigma^{\omega}(a)$ be a pure morphic sequence with $\sigma$ non-erasing.
\begin{enumerate}
	\item 	If $\sigma$ is everywhere-growing and
		\begin{enumerate}[i.]
			\item quasi-uniform, then\footnote{$f(n) \in \mathcal{O}(g(n))$ if $\exists C >0, n_0 \ \forall n \geq n_0 \ |f(n)| \leq |C g(n)|$.} $p_{\mathbf{w}}(n) \in \mathcal{O}(n)$;
			\item polynomially diverging, then $p_{\mathbf{w}}(n) \in \Theta(n \log \log n)$;
			\item exponentially diverging, then $p_{\mathbf{w}}(n) \in \Theta(n \log n)$.
		\end{enumerate}
	\item If $\sigma$ is not everywhere-growing and if there are infinitely many factors of $\mathbf{w}$ in $A_{\mathfrak{B}}^*$, then $p_{\mathbf{w}}(n)=\Theta(n^2)$.
	\item If $\sigma$ is not everywhere-growing and if there are only finitely many factors of $\mathbf{w}$ in $A_{\mathfrak{B}}^*$, then there exists a pure morphic sequence $\tau^{\omega}(b)$ with $\tau: B^* \to B^*$ everywhere-growing and a non-erasing morphism $\lambda: B^* \to A^*$ such that $\mathbf{w} = \lambda (\tau^{\omega}(b))$. In this case, we have $p_{\mathbf{w}}(n) \in \Theta(p_{\tau^{\omega}(b)}(n))$.  
\end{enumerate}
\end{theorem}

Unfortunately, Theorem~\ref{thm: pansiot} only holds for
non-erasing morphisms. However, the following result states that when
the morphism is erasing, the obtained pure morphic
sequence is a \textit{morphic sequence} (i.e., an image under a
morphism of a pure morphic sequence) with non-erasing morphisms. The
result is due to Cobham~\cite{Cobham_hartmanis} and was recovered
later by Pansiot~\cite{Pansiot_hierarchical}. It can also be found in
Cassaigne and Nicolas's survey~\cite{Cassaigne-Nicolas}.

\begin{theorem}[Cobham~\cite{Cobham_hartmanis} and Pansiot~\cite{Pansiot_hierarchical}]
\label{thm: cobham-erasing}
If $\mathbf{w}$ is a morphic sequence, it is the image under a letter-to-letter morphism of a pure morphic word $\sigma^{\omega}(a)$ with $\sigma$ a non-erasing morphism.
\end{theorem}

Theorems~\ref{thm: pansiot} and~\ref{thm: cobham-erasing} show that to
compute the complexity function of a pure morphic sequence, it is
sometimes necessary to view it as a morphic sequence. It is therefore
natural to be interested in the complexity function of such sequences.
By definition, any pure morphic sequence is morphic. The converse has been
known to be false since at least 1980, when Berstel proved that the
Arshon word is morphic but not pure morphic \cite{Berstel1980}. Other
examples can be found in the literature; for instance, the result by
S\'e\'ebold showing that the unique (up to letter permutation) binary
overlap-free word which is a fixed point of a morphism is the
Thue-Morse word \cite{Seebold1985}).

Moreover, it is not only the case that the
class of morphic sequences strictly contains the
class of pure morphic sequences, but also the asymptotic behavior of
their complexity functions are different. Indeed, Example~\ref{ex:
complexite n^{3/2}} shows that complexity classes given by
Pansiot are no longer sufficient.

\begin{example}[Deviatov~\cite{Deviatov}]
\label{ex: complexite n^{3/2}}
Let $\mathbf{w}$ be the morphic sequence $\tau(\sigma^{\omega}(0))$ where $\sigma$ and $\tau$ are defined by
\begin{eqnarray*}
	\sigma:	\begin{cases}
					0 \mapsto 01 \\
					1 \mapsto 12 \\
					2 \mapsto 23 \\
					3 \mapsto 3
				\end{cases}
	&
	\text{and}
	&
	\tau:	\begin{cases}
					0 \mapsto 0 \\
					1 \mapsto 1 \\
					2 \mapsto 2 \\
					3 \mapsto 2
				\end{cases}
\end{eqnarray*}
We have $p_{\mathbf{w}} \in \Theta(n \sqrt{n})$.
\end{example}

Other examples can be found in~\cite{Pansiot_subword}. Indeed, for all
$k \geq 1$, Pansiot explicitly built a morphic sequence $\mathbf{w}$
whose complexity function satisfies $p_{\mathbf{w}}(n) \in \Theta(n
\sqrt[k\,]{n})$. However, these behaviors $\Theta(n \sqrt[k\,]{n})$
seem to be the only new behaviors with respect to pure morphic
sequences. Indeed, in~\cite{Deviatov} Deviatov proved the next result
and conjectured an equivalent result of Pansiot's theorem
(Theorem~\ref{thm: pansiot}) for morphic sequences.

\begin{theorem}[Deviatov~\cite{Deviatov}]
\label{thm: Deviatov}
Let $\mathbf{w}$ be a morphic sequence. Then, either $p_{\mathbf{w}}(n) \in \Theta(n^{1+\frac{1}{k}})$ for some $k \in \mathbb{N}^*$, or $p_{\mathbf{w}}(n) \in \mathcal{O}(n \log n)$. 
\end{theorem}

\begin{conjecture}[Deviatov~\cite{Deviatov}]
The complexity function of any morphic sequence only adopts one of the following asymptotic behaviors: $\Theta(1)$, $\Theta(n)$, $\Theta(n \log \log n)$, $\Theta(n \log n)$, $\Theta(n^{1 + \frac{1}{k}})$ for some $k \in \mathbb{N}$.
\end{conjecture}

In particular, Theorem~\ref{thm: Deviatov} implies that the highest
complexity that one can get is the same for morphic sequences and for
pure morphic sequences. This can be explained by the following
result.

\begin{proposition}[Cassaigne and Nicolas~\cite{Cassaigne-Nicolas}]
\label{prop: cassaigne nicolas action morphisme sur une suite}
Let $\mathbf{w}$ be a one-sided sequence over $A$ and $\sigma:A^* \to B^*$ be a non-erasing morphism. If $M = \max_{a \in A} |\sigma(a)|$, for all $n$ we have $p_{\sigma(\mathbf{w})}(n) \leq M p_{\mathbf{w}}(n)$. Moreover, if $\mathbf{w}$ is pure morphic and $\sigma$ is injective, then $p_{\sigma(\mathbf{w})}(n) \in \Theta(p_{\mathbf{w}}(n))$.
\end{proposition}

It has been pointed out by a referee that Proposition~\ref{prop:
cassaigne nicolas action morphisme sur une suite} could be improved by
replacing the injectivity hypothesis with the following one: \textit{there
exists $K$ such that for all $u \in {\rm Fac}(\sigma(\mathbf{w}))$, we
have ${\rm Card}\left(\sigma^{-1}\left(\{u \}\right) \cap
L(\mathbf{w})\right) \leq K$}. Furthermore, the comparison between the
respective complexity of $\mathbf{w}$ and $\sigma(\mathbf{w})$ seems to
depend on the lack of injectivity of $\sigma$.

The previous discussion shows that the factor complexity of morphic
sequences is rather constrained. To conclude this section, we give some
examples of how some additional combinatorial criteria can 
restrict it even further.

A well-known fact is that if a pure morphic sequence is
\textit{$k$-power-free}, i.e., it does not contains any factor of the
form $u^k$, then its factor complexity grows at least linearly and at
most like $n \log n$ (see~\cite{D0L_m-free}). {We will consider a
similar criterion for $S$-adic sequences in Section}~\ref{subsection:
distinct powers}.

Another such criterion is the \textit{uniform recurrence} of the sequence, i.e., any factor occurs infinitely often and with bounded gaps in $\mathbf{w}$. For morphic sequences, this implies that the complexity is linear (see~\cite{Nicolas-Pritykin}).  
Actually, the uniform recurrence of a morphic sequence is even equivalent to its \textit{linear recurrence}, i.e., any factor $u$ occurs infinitely often and with gaps bounded by $K|u|$ (see~\cite{Durand_UR, Durand_preprint}). 
Furthermore, if $\mathbf{w}$ is a morphic and uniformly recurrent sequence over $A$, then $\mathbf{w}$ is a morphic sequence $\tau (\sigma^{\omega}(a))$ with $\sigma$ a primitive morphism (this result was already proved in~\cite{Durand_UR} in the particular case of morphic sequences $\psi(\varphi^{\omega}(a))$ with $\psi$ non-erasing and $\varphi$ everywhere-growing). The following result also provides an algorithm to check whether a pure morphic sequence is uniformly recurrent. 

\begin{theorem}[Damanik and Lenz~\cite{Damanik-Lenz}]
\label{thm: damanik lenz LR}
A pure morphic sequence $\mathbf{w} = \sigma^{\omega}(a)$ is uniformly recurrent if and only if there is a growing letter $b \in A$ that occurs with bounded gaps in $\mathbf{w}$ and such that for all letters $c \in A$ there is a power $\sigma^k$ such that $c$ occurs in $\sigma^k(b)$.
\end{theorem}

\subsection{$S$-adic sequences}
\label{subsection S-adic}

The previous section shows that the factor complexity of morphic
sequences is rather restricted (especially for pure morphic
sequences). In particular, the class of uniformly recurrent morphic
sequences is strictly contained in the class of morphic sequences with
linear complexity. In this section, we show that, for $S$-adic
sequences, the state of affairs is quite different.  The first important result
is the following.

\begin{proposition}[Cassaigne~\cite{Cassaigne_S-adic}]
\label{prop:Cassaigne adique}
Let $A$ be an alphabet and $l \notin A$. There exists a finite set $S$ of morphisms over $A' = A \cup \{l\}$ such that any sequence over $A$ is $S$-adic.
\end{proposition}


In particular,
this implies that any function which is the complexity function
of some sequence is also the complexity function of some $S$-adic sequence.
(although for morphic sequences, the complexity is at most quadratic).
Moreover, the following proposition implies that the set of possible
asymptotic behaviors for the complexity function of $S$-adic sequences
is uncountable (although it is finite for pure morphic sequences and
countable for morphic ones since the set of morphic sequences is
countable). See also \cite{Mauduit-Moreira} for another approach to
build sequences whose complexity is closed to a given function.


\begin{proposition}[Cassaigne~\cite{Cassaigne_intermediate}]
\label{prop: cassaigne complexite arbitraire}
Let $f: \mathbb{R}^+ \to \mathbb{R}^+$ be a function such that
\begin{enumerate}[i.]
	\item $\lim_{t \to +\infty} \frac{f(t)}{\log t} = +\infty$;
	\item $f$ is differentiable, except possibly at $0$;
	\item $\lim_{t \to +\infty} f'(t) t^{\beta} = 0$ for some $\beta > 0$;
	\item $f'$ is decreasing.
\end{enumerate}
Then there exists a uniformly recurrent sequence $\mathbf{w}$ over $\{0,1\}$ such that\footnote{$f(n) \sim g(n)$ if $\forall \varepsilon>0 \ \exists n_0 \ \forall n>n_0 \ |f(n)/g(n)-1|<\varepsilon$.} $\log(p_{\mathbf{w}}(n)) \sim f(n)$.
\end{proposition}

In particular, the function $f(n)$ in the previous proposition can be
taken equal to $n^{\alpha}$ for any $\alpha$ with $0 < \alpha < 1$.

Another big difference is that the class of uniformly recurrent
$S$-adic sequences with linear complexity forms a very small subset of
the class of uniformly recurrent $S$-adic sequences. Indeed, recall
that the \textit{topological entropy} of a sequence over an alphabet
$A$ is the real number $h$ with $0 \leq h \leq \log({\rm Card}(A))$
defined by
\[
	h = \limsup_{n \to \infty} \frac{\log (p(n))}{n}.
\]
A uniformly recurrent sequence $\mathbf{w}$ over an alphabet $A$ with
at least two letters $a,b \in A$ cannot have maximal complexity
($p_\mathbf{w}(n) = {\rm Card}(A)^n$): since all powers $a^n$ occur in
$\mathbf{w}$, there are unbounded gaps between two successive
occurrences of $b$ in $\mathbf{w}$. However, together with
Proposition~\ref{prop:Cassaigne adique}, the following result shows
that, except the maximal one $p_\mathbf{w}(n) = {\rm Card}(A)^n$, any
high complexity can be attained by uniformly recurrent $S$-adic
sequences.

\begin{theorem}[Grillenberger~\cite{Grillenberger}]
\label{thm: grillenberger}
Let $A$ be an alphabet with $d = {\rm Card}(A) \geq 2$ and $h \in \left[ 0, \log(d)\right[$. There exists a uniformly recurrent one-sided sequence $\mathbf{w}$ over $A$ with topological entropy $h$. 
\end{theorem}

The proof of previous theorem is furthermore constructive and Ferenczi
and Monteil noticed~\cite[Chap.\ 7]{CANT} that this construction is
$S$-adic with an infinite set $S$.

The following result provides an $S$-adic characterization of uniformly
recurrent sequences.  A sequence is said to be \textit{primitive
$S$-adic (with constant $s_0$)} if $s_0 \in \mathbb{N}$ is such that
for all $r \in \mathbb{N}$, all letters in $A_r$ occur in all images
$\sigma_r \cdots \sigma_{r+s_0}(a)$, $a \in A_{r+s_0+1}$.  It is said
to be \textit{weakly primitive $S$-adic}  if for all $r \in
\mathbb{N}$, there exists $s > 0$ such that all letters in $A_r$ occur
in all images $\sigma_r \cdots \sigma_{r+s}(a)$, $a \in A_{r+s+1}$. Any
primitive $S$-adic sequence is weakly primitive and
Durand~\cite{Durand_corrigentum} proved that any weakly primitive
$S$-adic sequence is uniformly recurrent. {Following a construction
based on return words (see Section}~\ref{subsection return words} {for
the definition), one can prove that the converse is true.} 
Recall that a sequence is said to be \textit{proper $S$-adic} if all
morphisms in its directive word are \textit{proper}, i.e., for all $n$
there are letters $a,b \in A_n$ such that $\sigma_n(A_{n+1}) \subset a
A_n^* b$.
Then we have

\begin{theorem}[Durand~\cite{Durand_corrigentum}, Leroy~\cite{Leroy_these}]
\label{thm: characterization S-adicity minimal}
A sequence $\mathbf{w}$ is uniformly recurrent if and only if it is weakly primitive $S$-adic.

Moreover, the directive word can be chosen to be proper and if $\mathbf{w}$ does not have linear complexity, then 
$S$ is infinite.
\end{theorem}

The proof is similar to the proof of the following result, which gives
an $S$-adic characterization of linearly recurrent sequences. 

\begin{theorem}[Durand~\cite{Durand_corrigentum}]
\label{thm: durand LR S-adic}
A sequence $\mathbf{w}$ is linearly recurrent if and only if it is primitive and proper $S$-adic with ${\rm Card}(S)< +\infty$.
\end{theorem}

The next example shows that the linear recurrence property is an even
stronger condition than primitivity for $S$-adic sequences  (contrary
to what holds in the morphic case).

\begin{example}[Durand~\cite{Durand_corrigentum}]
\label{ex: durand primitif S-adic pas LR}
Let $S = \{\sigma,\tau\}$ where $\sigma$ and $\tau$ are defined by
\begin{eqnarray*}
	\sigma:	\begin{cases}
				0 \mapsto 021	\\
				1 \mapsto 101	\\
				2 \mapsto 212
			\end{cases}
	&
	\text{and}
	&
	\tau:	\begin{cases}
				0 \mapsto 012	\\
				1 \mapsto 021	\\
				2 \mapsto 002
			\end{cases}	
\end{eqnarray*}
The sequence
\[
	\mathbf{w} = \lim_{n \to +\infty} \sigma \tau \sigma^2 \tau \cdots \sigma^n \tau (0^{\omega})
\]
is primitive $S$-adic but not linearly recurrent.
\end{example}


\section{$S$-adicity and linear complexity}
\label{section: s-adicity and linear}

The aim of this section is to explore some ideas that one might have
about the $S$-adic conjecture. First, we present some sufficient
conditions for $S$-adic sequences to have linear complexity, and we
show that we cannot make them weaker. Then, we give some
counterexamples to some conditions that one might naturally believe to
be sufficient to get linear complexity.

\subsection{The growth rate of the length}
\label{subsection croissance}

Durand~\cite{Durand_LR,Durand_corrigentum} gave some sufficient
conditions for an $S$-adic sequence to have linear complexity. The
main condition is the one given by the following result and is a
generalization of what exists for pure morphic sequences (see
Theorem~\ref{thm: pansiot}). The other conditions are simply
consequences of it.

\begin{proposition}[Durand~\cite{Durand_corrigentum}]
\label{prop: durand longueur comparable S-adic}
Let $\mathbf{w}$ be an $S$-adic sequence with ${\rm Card}(S)<+\infty$ and whose directive word is $(\sigma_n)_{n \in \mathbb{N}}$ with $\sigma_n: A_{n+1}^* \to A_n^*$ and $A_0$ the alphabet of $\mathbf{w}$. If there is a constant $D$ such that for all $n$,
\begin{equation}
\label{cond croissance S-adic}
	\max_{a,b \in A_{n+1}} \frac{|\sigma_0 \cdots \sigma_n(a)|}{|\sigma_0 \cdots \sigma_n(b)|} \leq D,
\end{equation}
then $p_{\mathbf{w}}(n) \leq D \max_{\sigma_n \in S, a \in A_{n+1}} |\sigma_n(a)| ({\rm Card}(A))^2 n$ with $A = \cup_{n \in \mathbb{N}}A_n$.
\end{proposition}

\begin{corollary}[Durand~\cite{Durand_corrigentum}]
\label{cor: durand uniform S-adic}
If $\mathbf{w}$ is $S$-adic with ${\rm Card}(S)< \infty$ and all morphisms in $S$ are uniform, then $p_{\mathbf{w}}(n) \leq l ({\rm Card}(A))^2 n$ with $A = \cup_{n \in \mathbb{N}}A_n$ and $l = \max\limits_{\sigma \in S, a \in A(\sigma)} |\sigma(a)|$.
\end{corollary}
 
\begin{proposition}[Durand~\cite{Durand_LR}]
\label{prop: durand primitive S-adic}
If $\mathbf{w}$ is a primitive $S$-adic sequence with ${\rm Card}(S)<+\infty$ and constant $s_0$ directed by $(\sigma_n)_{n \in \mathbb{N}}$ with $\sigma_n: A_{n+1}^* \to A_n^*$ and $A_0$ the alphabet of $\mathbf{w}$, then there exists a constant $D$ such that for all non-negative integers $r$, 
\[
	\max_{a,b \in A_{r+s_0+1}}\frac{|\sigma_r \cdots \sigma_{r+s_0}(a)|}{|\sigma_r \cdots \sigma_{r+s_0}(b)|} \leq D.
\]
\end{proposition}
  
\begin{corollary}
\label{cor: durand 1 morphisme fortement primitif}
Let $S$ be a set of non-erasing morphisms and $\tau \in S$ be strongly primitive (i.e., for all letters $a$ of $\tau(A)$, the letter
$a$ occurs in all images $\tau(b)$ for $b \in A$). Any $S$-adic sequence for which $\tau$ occurs infinitely often with bounded gaps in the directive word is uniformly recurrent and has linear complexity.
\end{corollary}

The everywhere-growing property can be naturally transposed to $S$-adic
sequences. But, contrary to what holds in the pure morphic case, under
that assumption, the condition given by Equation~\eqref{cond croissance
S-adic} is not equivalent to linear complexity. Indeed, even some
Sturmian sequences do not satisfy it (those with unbounded coefficients
$(k_n)_{n \in \mathbb{N}}$ in Example~\ref{ex: sturmian}). One might
therefore try to make that condition a little bit weaker.

We can observe in Example~\ref{ex: sturmian} that Condition~\eqref{cond
croissance S-adic} is still satisfied infinitely often. Indeed, let us
consider the  directive word $(\tau_n)_{n \in \mathbb{N}}$ defined by
$\tau_0 = L_0^{k_0} R_0^{k_1} L_1$, $\tau_{2n} = L_0^{k_{4n}-1}
R_0^{k_{4n+1}} L_1$ for $n \geq 1$ and $\tau_{2n+1} = L_1^{k_{4n+2}-1}
R_1^{k_{4n+3}} L_0$ for $n \geq 0$. For all $n$, there exist 
integers $i$ and $j$ such that either $\tau_n = [0^i10^{j+1},0^i10^j]$
or $\tau_n = [1^i01^j,1^i01^{j+1}]$. With these morphisms, we have
\begin{equation}
\label{eq: sturmian contracte}
	\tau_0 \tau_1 \cdots \tau_n \cdots = L_0^{k_0} R_0^{k_1} L_1^{k_2} R_1^{k_3} \cdots L_1^{k_{4n+2}} R_1^{k_{4n+3}} \cdots
\end{equation}
and there is a constant $K$ such that for all $n$, $\max_{a,b \in A_{n+1}} \frac{|\tau_0 \cdots \tau_n(a)|}{|\tau_0 \cdots \tau_n(b)|} \leq K$. The sequence $(\tau_n)_{n \in \mathbb{N}}$ is called a \textit{contraction} of the directive word $(L_0^{k_0} R_0^{k_1} \cdots)$. Observe that the set $S = \{\tau_n \mid n \in \mathbb{N}\}$ of morphisms might be infinite (when $(k_n)_{n \in \mathbb{N}}$ is unbounded). Consequently, it may be interesting to work either with infinite sets of morphisms or with contractions.

However, Example~\ref{ex: morse+n^2} below shows that
Proposition~\ref{prop: durand longueur comparable S-adic} is no longer true
when ${\rm Card}(S)=\infty$. Indeed, if we consider the
contraction $(\sigma_n)_{n \in \mathbb{N}}$ of the directive word of
Proposition~\ref{prop: morse+n^2} defined for all $n \geq 0$ by
\begin{equation}
\label{eq: morse+n^2 contr.acte}
	\sigma_n = \gamma^{k_n} \mu,
\end{equation}
we have $|\sigma_0 \cdots \sigma_n(0)| = |\sigma_0 \cdots \sigma_n(1)|$ for all $n$, although the complexity is no longer linear when 
the sequence $(k_n)_{n \in \mathbb{N}}$ is unbounded.

\begin{example} 
\label{ex: morse+n^2}
Let $\mu$ be the \textit{Thue-Morse morphism} $[01,10]$ and let $\gamma$ be the morphism $[001,1]$. From Theorem~\ref{thm: pansiot} we know that the non-uniformly recurrent sequence 
\[
	\gamma^{\omega}(0) = 001 001^2 001 001^3 001 001^2 001 001^4 \cdots  
\]
has quadratic complexity.
 
\begin{proposition}
\label{prop: morse+n^2}
Let $(k_n)_{n \in \mathbb{N}}$ be a sequence of non-negative integers. The sequence 
\[
	\mathbf{w}_{\gamma,\mu} = \lim_{n \to +\infty} \gamma^{k_0} \mu \gamma^{k_1} \mu \gamma^{k_2} \mu \cdots \gamma^{k_n} \mu (0^{\omega})
\]
is uniformly recurrent. Moreover, $\mathbf{w}_{\gamma,\mu}$ has at most linear complexity if and only if the sequence $(k_n)_{n \in \mathbb{N}}$ is bounded. Finally, for all $n$ we have 
\[
	|\gamma^{k_0} \mu \gamma^{k_1} \mu \gamma^{k_2} \mu \cdots \gamma^{k_n} \mu(0)| = |\gamma^{k_0} \mu \gamma^{k_1} \mu \gamma^{k_2} \mu \cdots \gamma^{k_n} \mu(1)|,
\]
and denoting
\[
	\ell_n = |\gamma^{k_0} \mu \gamma^{k_1} \mu \gamma^{k_2} \mu \cdots \gamma^{k_n} \mu(0)|,
\]
we have
\[
	p_{\mathbf{w}_{\gamma,\mu}}(\ell_n) \leq 3 \ell_n.
\]
\end{proposition}

Before proving the result, recall that a \textit{right} (resp.,
\textit{left}) \textit{special factor} in a language $L \subset A^*$ is
a factor such that there are at least two letters $a,b \in A$ for which
$ua$ and $ub$ (resp., $au$ and $bu$) belong to $L$.  A
\textit{bispecial factor} is a factor which is both left and right
special. This definition can be extended to words and sequences
$\mathbf{w}$ by replacing $L$ by the set of factors
${\rm Fac}(\mathbf{w})$. Let us recall
the following result.

\begin{theorem}[Cassaigne~\cite{Cassaigne_big_thm}]
\label{theorem: cassaigne diff de complexite}
A sequence has linear complexity if and only if there is a constant $K$ such that for all $n$, the number of right (resp., left) special factors of length $n$ is less than $K$.
\end{theorem}

\begin{proof}[Proof of Proposition~\ref{prop: morse+n^2}]
First, as $\mu$ occurs infinitely often in the directive word,
$\mathbf{w}_{\gamma,\mu}$ is weakly primitive $\{\gamma, \mu\}$-adic
and so, by Theorem~\ref{thm: characterization S-adicity minimal}, it is
uniformly recurrent.

Now let us study the complexity depending on the sequence $(k_n)_{n \in
\mathbb{N}}$. The case of a bounded sequence is a direct consequence of
Corollary~\ref{cor: durand 1 morphisme fortement primitif}. Hence, let
us assume that the sequence $(k_n)_{n \in \mathbb{N}}$ is unbounded and
let us show that the complexity is not at most linear. Due to
Theorem~\ref{theorem: cassaigne diff de complexite}, we only have to
prove that the number of right special factors of length $n$ of
$\mathbf{w}_{\gamma,\mu}$ is unbounded.

As already mentioned in Example~\ref{ex: morse+n^2}, the fixed point
$\gamma^{\omega}(0)$ has quadratic complexity. Consequently the number
of right special factors of $\gamma^{\omega}(0)$ of a length $n$ is
unbounded.

We let the reader verify that bispecial factors of $\gamma^\omega(0)$ are the
words $\varepsilon$, $0$, $1$ and the words $\gamma(1v)$ with $v$ bispecial,
and that other right special factors of $\gamma^\omega(0)$ are the suffixes of words $\gamma(v)$ for $v$ right special. Thus, by induction, one can state that all right special factors of length $n$ of 
 $\gamma^{\omega}(0)$ occur in $\gamma^{n+1}(0)$. 
 
Now let us show that if $u$ is a right special factor in
$\gamma^{k_{n+1}}(0)$, then $\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots
\gamma^{k_n} \mu (u)$ is a right special factor of $\mathbf{w}$ of
length $|u| 2^{q}$ with $q = \sum_{i = 0}^{n} (k_i +1)$.  Indeed, as
$\mu(0)$ and $\gamma(0)$ start with $0$ and $\mu(1)$ and $\gamma(1)$
start with $1$, the image of $u$ is still a right special factor.
Moreover, $\mu(u)$ contains exactly $|u|$ occurrences of the letter $0$
and $|u|$ occurrences of the letter $1$, and both $\gamma$ and $\mu$
map a word with the same number of $0$ and $1$ to a word of double
length with the same number of $0$ and $1$.  Hence $|\gamma^{k_0} \mu
\gamma^{k_1} \mu \cdots \gamma^{k_n} \mu (u)| = |u| 2^q$ with $q$
defined as previously. Now, if $u$ and $v$ are two distinct right
special factors of length $m$ of $\gamma^{\omega}(0)$, then
$\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu (u)$ and
$\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu (v)$ are two
distinct special factors of length $m 2^q$ of $\mathbf{w}$. As the
number of right special factors of a given length of
$\gamma^{\omega}(0)$ is unbounded, and as the sequence $(k_n)_{n \in
\mathbb{N}}$ is unbounded, the number of right special factors of a
given length of $\mathbf{w}$ is also unbounded, which concludes the
first part of the proof.

The last step is to show that, for all integers $\ell_n$, we have
$p_{\mathbf{w}_{\gamma,\mu}}(\ell_n) \leq 3 \ell_n$. For all
non-negative integers $n$, we already know that
\[
	|\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(0)| = |\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(1)| = \ell_n = 2^q.
\]
with $q$ as defined previously by $\sum_{i = 0}^n (k_i +1)$. Consequently, all factors $u$ of length $\ell_n$ are factors of $|\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(v)|$ for some word $v$ of length 2. As there are only 4 possible binary words of length 2 and as there are no more than $\ell_n+1$ distinct factors of length $\ell_n$ in a word of length $2\ell_n$, we obtain $p_{\mathbf{w}_{\gamma,\mu}}(\ell_n) \leq 4\ell_n +4$. However, it is easily deduced from the following equations that the sets of factors of length $\ell_n$ that respectively occur in $\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(00)$ and in $\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(11)$ are equal. 
\begin{eqnarray*}
	\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(00)
	&=&
	\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_{n-1}} \mu \left( \gamma^{k_n}(0) 1 \gamma^{k_n}(0) 1 \right)	\\
	\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(11)
	&=&
	\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_{n-1}} \mu \left( 1 \gamma^{k_n}(0) 1 \gamma^{k_n}(0) \right)	
\end{eqnarray*}
Consequently,  we obtain $p_{\mathbf{w}_{\gamma,\mu}}(\ell_n) \leq 3 \ell_n +3$. But, among the $3\ell_n +3$ words, both words $\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(0)$ and $\gamma^{k_0} \mu \gamma^{k_1} \mu \cdots \gamma^{k_n} \mu(1)$ have been counted several times (twice for one of them and four times for the other). 
Hence $p_{\mathbf{w}_{\gamma,\mu}}(\ell_n) \leq 3\ell_n-1$.
\end{proof}
\end{example}


\subsection{The condition $C$ of the conjecture might not only concern the set $S$}
\label{subsection: condition C}

Since it seems hard to make the condition of Equation~\eqref{cond
croissance S-adic} weaker, another idea is to determine new sufficient
conditions that are independent of it.  The first attempt in this
direction was proposed by Boshernitzan. He asked  whether the following
holds:
\textit{if $S$
contains only morphisms for which the fixed points (if it exists) of
their powers have linear complexity, then any $S$-adic sequence has
linear complexity}.

But Boshernitzan eventually provided the following counterexample to
that statement. Since we did not find any detailed proof of it in the
literature, we provide it below.

\begin{example}
\label{ex: n^2}
Let $\gamma$ and $E$ be the morphisms over $\{0,1\}$ respectively defined by $[001,1]$ and $[1,0]$. Observe that both morphisms $\gamma E$ and $E \gamma$ are \textit{primitive}. Consequently, they admit a power whose fixed points have linear complexity. We consider the  sequence 
\[
	\mathbf{w}_{\gamma,E} = \lim_{n \to + \infty} \gamma E \gamma^2 E \gamma^3 E \cdots \gamma^{n-1} E \gamma^n(0^{\omega}).
\]

\begin{proposition}[Boshernitzan]
\label{prop: n^2}
The sequence $\mathbf{w}_{\gamma,E}$ is $S$-adic for $S = \{ \gamma E, E \gamma\}$.  Further, it is uniformly recurrent and does not have linear complexity.
\end{proposition} 


\begin{proof}
First, by definition, $\mathbf{w}_{\gamma,E}$ is indeed $S$-adic for $S= \{ \gamma E, E \gamma\}$. 

Next, the composition $\gamma E \gamma$ is strongly primitive and
occurs infinitely often in the directive word of
$\mathbf{w}_{\gamma,E}$. It is therefore a consequence of
Theorem~\ref{thm: characterization S-adicity minimal} that
$\mathbf{w}_{\gamma,E}$ is uniformly recurrent.

To prove that $\mathbf{w}_{\gamma,E}$ does not have linear complexity, by Theorem~\ref{theorem: cassaigne diff de complexite}, it is sufficient to prove that the number of its right special factors of length $n$ is unbounded. For this purpose, let us introduce notation. For all $k \in \mathbb{N}^*$, let us define the morphism $\Gamma_k = \gamma E \gamma^2 E \cdots \gamma^{k-1} E \gamma^k E$ and, for all $k \in \mathbb{N}$, the sequence
\[
	\mathbf{w}^{(k)} = \lim_{n \to + \infty} \gamma^{k+1} E \gamma^{k+2} E \cdots \gamma^{k+n-1} E \gamma^{k+n}(0^{\omega}).
\]

We then have $\mathbf{w}_{\gamma,E} = \mathbf{w}^{(0)} = \Gamma_k (\mathbf{w}^{(k)})$, for all $k \geq 1$. For all $i \geq 1$ we also consider the word $u_i = \gamma^i(10) = 1 \gamma^i(0)$. As $100$ and $101$ are factors of $E(\mathbf{w}^{(k+1)})$, and as $100$ and $001$ are factors of $\gamma^{k-j}\gamma(E(\mathbf{w}^{(k+1)}))$ for all $j$ with $1 \leq j \leq k$ (observe also that $\gamma(100)= \gamma(10)001$ and $\gamma(001) = 00\gamma(10)1$), we can deduce  that $u_i$ is a right special factor of $\mathbf{w}^{(k)}$ for all $i$ with $1 \leq i \leq k+1$.
As words $\Gamma_k(0)$ and $\Gamma_k(1)$ start with different letters, for all integers $i$ such that $1 \leq i \leq k+1$, the word $\Gamma_k(u_i)$ is a right special factor of $\mathbf{w}_{\gamma,E}$, and so are all of its suffixes.

For $1 \leq i \leq k+1$, the word $u_i$ end with $1001^i$, so that the longest common suffix between $u_i$ and 
$u_{i+1}$ is $1^i$. It follows that the longest common suffix between $\Gamma_k(u_i)$ and $\Gamma_k(u_{i+1})$ is the word $p_k\Gamma_k(1^i)$ where $p_0 = \varepsilon$ and for $k \geq 1$,
\[
	p_k = 1 \Gamma_1(1^2)\Gamma_2(1^3)\cdots \Gamma_{k-1}(1^k).
\]
This is indeed a consequence of the fact (we let the reader verify it) that for any word $u$ containing at least one occurrence of $0$ and $1$, the word $\Gamma^k(u)$ ends with $ap_k$ where $a$ is the last letter of $u$ when $k$ is even, and where $a$ is the opposite letter to the last letter of $u$ when $k$ is odd.

 From what precedes $\mathbf{w}_{\gamma,E}$ has at least $n(k)$ right special words of length $|p_k\Gamma_k(1^k)|+1$, where $n(k)$ denotes the number of integers $i$ between $1$ and $k+1$ such that $|\Gamma(u_i)| > |p_k\Gamma_k(1^k)|$. Next fact allows to estimate $n(k)$.

\textit{Fact}: With $f(k) = \frac{k^2+k+2}{2}$, for all $k \geq 2$,
\begin{enumerate}
\item for all $1 \leq i \leq k+1$, $|\Gamma_k(u_i)| = 2^i 2^{f(k)}$,
\item $|p_k\Gamma_k(1^k)| \leq k^2 2^{f(k)}$.
\end{enumerate}


\begin{proof}[Proof of the fact]

1. Let $i$ be between $1$ and $k+1$. By induction, one can verify that $|\gamma^i(0)|_0 = 2^i$ and  $|\gamma^i(0)|_1 = 2^i-1$. As $u_i = 1 \gamma^i(0)$, we have $|u_i|_0 = |u_i|_1 = 2^i$. Observe that for any word $v$ such that $|v|_0 = |v|_1$, we have $|\gamma(v)| = 2 |v|$ and $|\gamma(v)|_0 = |\gamma(v)|_1 = |v|$ and $|E(v)|_0 = |E(v)|_1 = |v|_0$.  

Thus, as  $\Gamma_k = \gamma E \gamma^2 E \cdots \gamma^{k-1} E \gamma^k E$, $|\Gamma_k(u_i)| = 2^{i+1} 2^{\sum_{j=1}^k j} = 2^{i+1} 2^{\frac{k(k+1)}{2}} = 2^i 2^{f(k)}$. 

2. Before estimating $|p_k\Gamma_k(1^k)|$, we need an estimate of $|\Gamma_k(1)|$.
\begin{eqnarray*}
	|\Gamma_k(1)| 	&=& \left| \gamma E \gamma^2 E \cdots \gamma^k E (1) \right|	\\
					&=&	\left| \gamma^k(0)\right|_0 \left| \gamma E \gamma^2 E \cdots \gamma^{k-1} E(0) \right| 	
						+ \left| \gamma^k(0)\right|_1 \left| \gamma E \gamma^2 E \cdots \gamma^{k-1} E(1) \right| \\
					&=& 2^k \left( \left| \Gamma_{k-1}(01) \right| - \left| \Gamma_{k-1}(1) \right| \right)
						+ \left( 2^k -1 \right) \left| \Gamma_{k-1}(1) \right|	\\
					&=&	2^{\frac{k^2+k+2}{2}} - \left| \Gamma_{k-1}(1) \right| < 2^{f(k)}.
\end{eqnarray*}
Observe that $|\Gamma_k(1^k)| = k |\Gamma_k(1)|$. One can verify that, for all $j$ with $1 \leq j \leq k$, $\Gamma_{j-1}(1^j) \leq \Gamma_k(1^k)$. Moreover as $k \geq 2$, $|1\Gamma_1(1^2)|\leq |\Gamma_k(1^k)|$.

Hence $|p_k\Gamma_k(1^k)| = |1\Gamma_1(1^2)|+\sum_{j=3}^{k}|\Gamma_{j-1}(1^j)|+|\Gamma_k(1^k)| < k|\Gamma_k(1^k)| < k^2f(k)$.
\end{proof}

To end the proof of proposition~\ref{prop: n^2}, it suffices to notice that for all $i$ such that $\log_2 k^2 < i \leq k+1$, 
$|\Gamma_k(u_i)| > |p_k\Gamma_k(1^k)|$, so that $n(k) \geq k+1- \left\lceil \log_2 k^2 \right\rceil$. In other words, the number of right special words of $\mathbf{w}_{\gamma,E}$ of length $|p_k\Gamma_k(1^k)|+1$ is unbounded, which shows by Theorem~\ref{theorem: cassaigne diff de complexite} that $\mathbf{w}_{\gamma,E}$ does not have linear complexity.
\end{proof}

\begin{remark}
The previous result is even stronger than just considering sets $S$ of morphisms with fixed points of linear complexity. Indeed, the sequence also has \textit{bounded partial quotients}, i.e., all morphisms occur with bounded gaps in the directive word (over $\{\gamma E, E \gamma\}$). 
\end{remark}
\end{example}

The opposite question to the one previously answered is to ask whether
$S$-adic sequences can have linear complexity when $S$ contains a
morphism that admits a fixed point which does not have linear
complexity. Example~\ref{ex: morse+n^2} positively answers that
question, and we can prove even more. Indeed, the following example
provides a uniformly recurrent $S$-adic sequence with linear
complexity such that a ``bad'' morphism occurs with arbitrary high
powers in its directive word.

\begin{example}
\label{ex: beta M}
Let us consider the morphisms
\begin{eqnarray*}
	\beta : \begin{cases}
				0 \mapsto 010	\\
				1 \mapsto 1112	\\
				2 \mapsto 2
			\end{cases}
	&
	\text{ and }
	&
	M :	\begin{cases}
			0 \mapsto 0	\\
			1 \mapsto 1 \\
			2 \mapsto 1
		\end{cases}
\end{eqnarray*}
and the sequence 
\[
	\mathbf{w}_{\beta,M} = \lim_{n \to +\infty} M \beta M \beta^2 M \beta^3 M \cdots \beta^{n-1} M \beta^n(0^{\omega}).
\]
Note that $\beta$ is not everywhere-growing; its set of bounded letters is $A_{\mathfrak{B},\beta} = \{2\}$ and all words in $A_{\mathfrak{B},\beta}^*$ are factors of $\beta^\omega(0)$. Hence by Theorem~\mbox{\ref{thm: pansiot}(2)}, $p_{\beta^\omega(0)}$ is in $\theta(n^2)$.
\end{example}

\begin{proposition}
\label{prop: beta n^2}
The sequence $\mathbf{w}_{\beta,M}$ defined just above has linear complexity. More precisely, for all $n$ we have $p(n+1)-p(n) \in \{1,2\}$.
\end{proposition}

The proof of this proposition uses the link,
proved by Cassaigne \cite{Cassaigne_resume},
between bispecial factors and the first difference $s$ of the complexity function. Given an infinite word $\mathbf{w}$, we recall that the  \textit{bilateral order} of a word $u$ is the value
\[
 	m(u) = {\rm Card} ({\rm Fac}(\mathbf{w}_{\beta,M}) \cap A u A) - {\rm Card}({\rm Fac}(\mathbf{w}_{\beta,M}) \cap Au) - {\rm Card}({\rm Fac}(\mathbf{w}_{\beta,M}) \cap uA) +1.
\]
When $m(u)>0$, the word $u$ is a bispecial factor of $\mathbf{w}$ called a \textit{strong bispecial} factor, and
when $m(u)<0$, the word
$u$ is also a bispecial factor of $\mathbf{w}$ called a \textit{weak bispecial} factor.

Let $s_\mathbf{w}$ (or simply $s$) be the function defined for $n \geq 0$ by $s(n) = p(n+1)-p(n)$. We have $s(0)=1$,
and Cassaigne proved (see~\mbox{\cite{Cassaigne_resume}}) that
\begin{equation}
\label{eq:cassaigne}
	s(n+1) - s(n) = \sum_{u \in {\rm Fac}_n(\mathbf{w})} m(u)
\end{equation}

In the 
next useful result, $\mathcal{B}_0$ is the identity morphism and,
for $k > 0$, we have $\mathcal{B}_k = M \beta M \beta^2 \cdots M \beta^k$.

\begin{lemma}
\label{lem:w beta M}
A word $u$ is a strong bispecial factor of $\mathbf{w}_{\beta,M}$ if and only if $u = \mathcal{B}_k M \beta^i(1)$ for some $k \geq 0$ and some $i$ in $\{0, \ldots, k\}$.

A word $u$ is a weak bispecial factor of $\mathbf{w}_{\beta,M}$ if and only if $u = \mathcal{B}_k M \beta^i(101)$ for some $k \geq 0$ and some $i$ in $\{0, \ldots, k\}$.
\end{lemma}

\begin{proof}
For all integers $k \geq 0$,
let  $\mathbf{w}^{(k)}$ be the sequence $\mathbf{w}^{(k)}$ whose directive word is 
$(M,$ $\beta^{k+1},$ $M,$ $\beta^{k+2},\dots)$. Note that, for $k \geq 0$, $\mathbf{w}_{\beta,M} = \mathcal{B}_k(\mathbf{w}^{(k)})$.

All words $010$, $011$, $110$, $111$ occur in $\mathbf{w}^{(k+1)}$ and
all words $010$, $011$, $120$, $111$ occur in
$\beta^j(\mathbf{w}^{(k+1)})$ for $j \geq 1$. Thus $M\beta^i(1)$ for
$i$ in $\{0, 1, \ldots, k+1\}$ are strong bispecial factors of
$\mathbf{w}^{(k+1)}$ (observe that $M\beta^i(120) = M\beta^i(210)$ contains
the factor $1M\beta^i(1)0$). As $\mathcal{B}_k(0)$ starts and ends with
$0$, and as $\mathcal{B}_k(1)$ starts and ends with $1$, $\mathcal{B}_k
M\beta^i(1)$ for $i \in \{0, 1, \ldots, k\}$ are strong bispecial
factors of $\mathbf{w}_{\beta,M}$.

Now let $i \in \{0, 1, \ldots, k\}$.  The words $0 M\beta^i(101)1$ and
$1M\beta^i(101)0$ are factors of $\mathbf{w}^{(k)}$ (respectively
factors of $M\beta^{i+1}(01)1$ and $1M\beta^{i+1}(10)$). So
$0\mathcal{B}_k(M\beta^i(101))1$ and $1 \mathcal{B}_k(M\beta^i(101)) 0$
are factors of $\mathbf{w}_{\beta,M}$.  One can verify that the
existence of the factor $0\mathcal{B}_k(M\beta^i(101))0$ in
$\mathbf{w}_{\beta,M}$ would imply the existence of factors
$M(0\beta^j(101)0)$ in $\beta^{(k+1-j)}(\mathbf{w}^{(k+1)})$ for $0
\leq j \leq i$, and the existence of the factor $01010$ in
$\beta^{(k+1-i)}(\mathbf{w}^{(k+1)})$, which is impossible.  Similarly
the existence of the factor $1\mathcal{B}_k(M\beta^i(101))1$ in
$\mathbf{w}_{\beta,M}$ would imply the existence of $11011$ in
$\beta^{(k+1-i)}(\mathbf{w}^{(k+1)})$, which is also impossible.

We now prove that there are no other strong and weak bispecial factors.
Let $u$ be a bispecial factor of $\mathbf{w}_{\beta,M}$. If $u$ contains no occurrence of the letter $0$, then $u = 1^n$ for some $n \geq 0$.
As $\mathbf{w}_{\beta,M}$ contains arbitrarily large powers of $1$ and infinitely many occurrences of $0$, the 
words $11^n1$, $01^n1$, $11^n0$ are all factors of $\mathbf{w}_{\beta,M}$. When $01^n0$ is a factor of $\mathbf{w}_{\beta,M}$, one can verify that $1^n = \mathcal{B}_kM\beta^i(1)$ for some $k \geq 0$ and some integer $i$ in $\{0, \ldots, k\}$. Thus $1^n$ is a strong bispecial factor of $\mathbf{w}_{\beta,M}$ if and only if $1^n = \mathcal{B}_kM\beta^i(1)$ for some $k \geq 0$ and some integer $i$ in $\{0, \ldots, k\}$.

Note that any factor of $\mathbf{w}_{\beta,M}$ containing only one
occurrence of $0$ is of the form $01^n$, $101^n$, $1^n0$ or $1^n01$ for
some $n \geq 0$, and is not bispecial.

Thus assume $u$ contains at least two occurrences of $0$. From the
form of the morphisms $\mathcal{B}_k$, there is a unique integer $k$
and a unique sequence of words
\[
	v, p_0, s_0, p_1, s_1, \dots, p_{k-1}, s_{k-1}
\]
over $\{0,1\}$ such that 
\[
	u = p_0 \mathcal{B}_1(p_1) \mathcal{B}_2(p_2) \cdots \mathcal{B}_{k-1}(p_{k-1}) \mathcal{B}_k(v) \mathcal{B}_{k-1}(s_{k-1}) \cdots \mathcal{B}_2(s_2) \mathcal{B}_1(s_1)s_0,
\]
where $v$ is a proper factor of $M\beta^{k+1}(010)$ and for all $i$, $0 \leq i \leq k-1$, the word $p_i$ (resp., $s_i$) is a suffix (resp., prefix) of $\mathcal{B}_{i+1}(0)$ or of $\mathcal{B}_{i+1}(1)$ but is neither equal to $\mathcal{B}_{i+1}(0)$ nor equal to $\mathcal{B}_{i+1}(1)$.

Since for all $i$, $\mathcal{B}_i(0)$ and $\mathcal{B}_i(1)$ do not have any common prefix or suffix, the factor $u$ is bispecial if and only if all words $p_0,s_0,p_1,s_1,\dots,p_{k-1},s_{k-1}$ are empty words and $v$ is bispecial in $\mathbf{w}^{(k)}$. Moreover, $v$ contains an occurrence of the letter $0$. We also have that $u$ is strongly (resp., weakly) bispecial if and only if $v$ is
also. Then it can be easily verified that the only bispecial factors in $\mathbf{w}^{(k)}$ that contain an occurrence of $0$ and that are factors of $M\beta^{k+1}(010)$ are the words $M \beta^i(101)$ for $i \in \{0,1,\dots,k\}$, which are weak bispecial factors.
\end{proof}

\begin{proof}[Proof of Proposition~\ref{prop: beta n^2}]
Let $(u_n)_{n \geq 0}$ be the sequence of strong and weak bispecial factors of $\mathbf{w}_{\beta,M}$.
Observe that, for all $k \geq 0$,
\begin{itemize}
\itemsep0cm
\item $\mathcal{B}_k M \beta^{k+1}(1) = \mathcal{B}_{k+1}(1) = \mathcal{B}_{k+1}M\beta^0(1)$. 
\item $|\mathcal{B}_k(M\beta^i(1))| < |\mathcal{B}_k(M\beta^i(101))| < |\mathcal{B}_k(M\beta^{i+1}(1))|$, for all $i$ in $\{0, 1, \ldots, k\}$.
\end{itemize}
Therefore, by Lemma~\mbox{\ref{lem:w beta M}}, the word $u_n$ is a
strong bispecial factor of $\mathbf{w}_{\beta,M}$ if $n$ is even, and
it is a weak bispecial factor of $\mathbf{w}_{\beta,M}$ if $n$ is odd.
As for any factor $u$ we have $m(u) =1$ if it is strong bispecial,
$m(u) = -1$ if
it is weak bispecial, and $m(u) = 0$ otherwise, by
Formula~\mbox{\ref{eq:cassaigne}}, for all $n \geq 0$, we have
\begin{itemize}
\itemsep0cm
\item $s(|u_n|+1)-s(|u_n|) = 1$ if $n$ is even,
\item $s(|u_n|+1)-s(|u_n|) = -1$ if $n$ is odd,
\item $s(n+1)-s(n) = 0$ if $n \not \in \{ |u_m| \mid m \geq 0\}$.
\end{itemize}
Consequently, since $s(0) = p(1)-p(0)= 1$, for all $n \geq 0$, we have $p(n+1)-p(n) = s(n) \in \{1,2\}$.
\end{proof}

\subsection{Another (easier?) version of the $S$-adic conjecture}

A natural idea to try to understand the $S$-adic conjecture is to consider
examples composed of well-known morphisms.

\begin{example}
The Sturmian word which is the fixed point of the \textit{Fibonacci morphism} $\varphi = [01,0]$ 
and the Thue-Morse word which is the fixed point of the \textit{Thue-Morse morphism} $\mu = [01,10]$ 
both have linear complexity. 
\end{example}

\begin{proposition}
\label{proposition: fibo+TM}
If $S = \{\varphi, \mu\}$,
where $\varphi$ and $\mu$ are defined above,
any $S$-adic sequence is linearly recurrent.
\end{proposition}

\begin{proof}
Let $S = \{ \mu, \varphi\}$.
Let $\mathbf{w}$ be an $S$-adic sequence directed by $(\sigma_n)_{n \in \mathbb{N}}$ and, for all $k \in \mathbb{N}$, let $\mathbf{w}^{(k)}$ be the $S$-adic sequence directed by $(\sigma_n)_{n \geq k}$.

By the definition of $\varphi$ and $\mu$, as  $\mathbf{w}^{(k)} \in \{\varphi(\mathbf{w}^{(k+1)}), \mu(\mathbf{w}^{(k+1)})\}$, the word $111$ does not occur in $\mathbf{w}^{(k)}$ for all $k \geq 1$. 
Note also that  $000$ does not occur in $\mu(\{0,1\}^*)$, and $0000$
does not occur in $\varphi(\mathbf{w}^{(k+1)})$, since otherwise $111$
would occur in $\mathbf{w}^{(k+1)}$. Thus,
for all $k \geq 0$,
neither $0000$ nor $111$
occurs in $\mathbf{w}^{(k)}$.
This implies
that the gap between two occurrences of $01$ and $10$ is at most 5 (7
is the maximal length of a shortest word of the form $10u10$ or of the
form $01u01$).

Now observe that $11$ occurs in $\mathbf{w}^{(k)}$ only in the image of
$\sigma_k(10)$ (and only if $\sigma_k = \mu$). This implies that the
gap between two consecutive occurrences of $11$ is at most $12$.

Finally observe that $00$ occurs in $\mathbf{w}^{(k)}$ only in the
image of $\sigma_1(10)$ or in the image of $\sigma_k(11)$ (when
$\sigma_k = \varphi$). As any factor of $\mathbf{w}^{(k)}$ that starts with
$10$ or $11$, ends with $10$ or $11$, and does not contain any other
occurrences of $10$ or $11$ has length at most $7$, the gap between
two consecutive occurrences of $00$ is at most 12.

We have just proved that the length of the largest gap between two occurrences of a word of length $2$ in all words $\mathbf{w}^{(k)}$ is bounded. By the
choice of $S$, we see that $\mathbf{w}$ is primitive $S$-adic.
Hence by a result of Durand~\cite{Durand_corrigentum}, we know that
$\mathbf{w}$ is linearly recurrent.
\end{proof}

Let us say that a set of morphisms $S$ is \textit{good-adic} if all $S$-adic sequences have linear complexity.
Proposition~\mbox{\ref{proposition: fibo+TM}} provides an example of such a set. Many other examples are known.  For example:
\begin{itemize}
	\item any singleton $\{ f \}$ with $f$ a morphism with fixed points of linear complexity;
	\item	the set of Sturmian morphisms $\{[01,1],[10,1],[0,01],[0,10]\}$;
	\item	the set of episturmian morphisms over an alphabet $A$: $S = \{ L_a, R_a \mid a \in A \}$ with for all $a \in A$, $L_a(a)=R_a(a) = a$, $L_a(b)=ab$ and $R_a(b)=ab$ for $b \neq a$;
	\item 	any finite set $S$ that contains only uniform morphisms (see Corollary~\ref{cor: durand uniform S-adic});
	\item 	any finite set $S$ that contains only strongly primitive morphisms (see Corollary~\ref{cor: durand 1 morphisme fortement primitif}).
\end{itemize}

Note that if $S$ is good-adic then, for any morphism $f$ in $S$
admitting an infinite fixed point, this fixed point must have linear
complexity. But this necessary condition is certainly not the only
one.

\begin{question}
What are good-adic sets of morphisms?
\end{question}

\subsection{About return words}
\label{subsection return words}

If $u$ is a factor of a sequence $\mathbf{w}$, a \textit{(left) return word} to $u$ is a word $r$ such that $ru$ is a factor of $\mathbf{w}$ having $u$ as a prefix and containing only two occurrences of $u$.
Return words to $u$ in $\mathbf{w}$ actually correspond to the gaps
between two consecutive occurrences of $u$ in $\mathbf{w}$.

Durand \mbox{\cite{Durand_UR}} proved that primitive {morphic}
sequences, i.e., sequences defined as the image, under a morphism, of a
fixed point of a primitive morphism, can be characterised using return
words. Hence, it is quite natural to ask whether such a result exists
for $S$-adic sequences with linear complexity.

There exist many examples of $S$-adic sequences $\mathbf{w}$ with linear complexity for which there exists an integer $K$ such that all factors of $\mathbf{w}$ have at most $K$ return words.
For instance, Vuillon~\mbox{\cite{Vuillon_sturmian}} proved that
Sturmian sequences are exactly the sequences whose  factors have
exactly two return words. Justin and Vuillon
\mbox{\cite{Justin-Vuillon}} extended this result to the family of
Arnoux-Rauzy sequences (also called {\it strict episturmian sequences}) whose
factors have exactly $m$ return words, with $m$ the cardinality of the
alphabet. Balkov\'{a}, Pelantov\'{a} and
Steiner~\mbox{\cite{Balkova-Pelantova-Steiner}} characterized sequences
that do not contain any weak bispecial factors and whose factors have
the same number of return words by showing they all have linear
complexity. Improving a result by Ferenczi~\mbox{\cite{Ferenczi}},
Leroy~\mbox{\cite{Leroy_these}} proved that sequences whose complexity
satisfies $1 \leq p(n+1)-p(n) \leq 2$ for all sufficiently large $n$
are $S$-adic and
{infinitely many} of their factors admit two or three return words.

Despite the previous example, the next proposition shows that there exist
$S$-adic sequences with linear complexity {such  that any long
factor has many return words (``many'' depending on ``long'').}

\begin{example}
\label{ex: plein de mots de retours}
Let us consider the three morphisms $p$, $\sigma$ and $s$ defined by
\begin{eqnarray*}
	p :	\begin{cases}
			a_1 \mapsto 0	\\
			a_2 \mapsto 1	\\
			b_1 \mapsto 1	\\
			b_2 \mapsto 0	
		\end{cases}
	\quad 
	\sigma :	\begin{cases}
					a_1 \mapsto a_1 a_2 a_1	\\
					a_2 \mapsto a_2 a_2 a_2	\\
					b_1 \mapsto b_1 b_2 b_1	\\
					b_2 \mapsto b_2 b_2 b_2	
				\end{cases}
	\quad
	s :	\begin{cases}
			0 \mapsto a_1	\\
			1 \mapsto b_1
		\end{cases}
\end{eqnarray*}
For all $n \geq 1$ we let $\pi_n$ denote the morphism $p \sigma^n s$. Then
we have
\[
	\pi_n : \begin{cases}
				0 \mapsto 0 1^{\mathbf{e}_0} 0 1^{\mathbf{e}_1} 0 1^{\mathbf{e}_2} \cdots = \left( \prod_{i = 0}^{2^{n-1}-1}  0 1^{\mathbf{e}_i} \right) 0 	\\
				1 \mapsto 1 0^{\mathbf{e}_0} 1 0^{\mathbf{e}_1} 1 0^{\mathbf{e}_2} \cdots = \left( \prod_{i = 0}^{2^{n-1}-1}  1 0^{\mathbf{e}_i} \right) 1 	\\
			\end{cases},
\]
where $\mathbf{e}$ is the fixed point of the morphism ${\rm Exp}$ defined over the infinite alphabet $\{ 3^n \mid n \in \mathbb{N}\}$ by
\[
	\forall n \in \mathbb{N}, \quad  {\rm Exp}(3^n) = 1 3^{n+1}, 	
\]
i.e.,
\[
	\mathbf{e} = 1 3 1 3^2 1 3 1 3^3 1 3 1 3^2 1 3 1 3^4 1 3 1 3^2 1 3 1 3^3 1 3 1 3^2 1 3 \cdots.
\]
Now let us consider the sequence 
\[
	\mathbf{w}_{\pi} = \lim_{n \to + \infty} \pi_1 \pi_2 \cdots \pi_n (0^{\omega}).
\]

\begin{proposition}
The sequence $\mathbf{w}_{\pi}$ defined above is uniformly recurrent, has 
linear complexity and for all integers $k$, there is a length $\ell_k$ such that all factors of $\mathbf{w}_{\pi}$ of length at least $\ell_k$ have at least $k$ return words in $\mathbf{w}_{\pi}$.
\end{proposition}

\begin{proof}
Uniform recurrence is
a direct consequence of Theorem~\ref{thm: characterization S-adicity minimal}.
Since $\mathbf{w}$ is $S$-adic with $S = \{p,\sigma,s\}$, it is a
consequence of Corollary~\ref{cor: durand uniform S-adic} that
$\mathbf{w}_{\pi}$ has linear complexity.

Let us prove that all sufficiently long factors of $\mathbf{w}_{\pi}$ have many return words. For all $k \geq 1$, we let $\mathbf{w}^{(k)}$ denote the sequence
\[
	\mathbf{w}^{(k)} = \lim_{n \to \infty}	\pi_k \pi_{k+1} \cdots \pi_n (0^{\omega}).
\]
We obviously have $\mathbf{w}^{(1)} = \mathbf{w}_{\pi}$ and for all $k \geq 1$, $\mathbf{w}_{\pi} = \pi_1 \cdots \pi_k (\mathbf{w}^{(k+1)})$. We also have $|\pi_k(0)| = |\pi_k(1)| = 3^k$ for all $k$ and we let $\ell_k$ denote the length
\[
	|\pi_1 \pi_2 \cdots \pi_k(0)| = |\pi_1 \pi_2 \cdots \pi_k(1)| = 3^{\frac{k(k+1)}{2}}.
\]

Due to the form of the morphisms $\pi_1$, any factor $u$ of $\mathbf{w}_\pi$ of length at least equal to $24$ can be uniquely decomposed into images $\pi_1(0)$ and $\pi_1(1)$, i.e., there is a unique word $v$ in $\mathbf{w}^{(2)}$ such that $u \in {\rm Fac}(\pi_1(v))$ and such that if $u \in {\rm Fac}(\pi_1(v'))$, then $v \in {\rm Fac}(v')$. Indeed, given such a factor $u$, either it contains an occurrence of $00$ or of $11$ (which uniquely determine how to decompose the factor), or it is equal to $\pi_1(10101010)$ or to $\pi_1(01010101)$ (neither $101010101$, nor $010101010$ occur in $\mathbf{w}^{(2)}$).

Similarly, we see that, for all $k \geq 2$, any factor of
$\mathbf{w}^{(k)}$ of length at least equal to $7$ can be uniquely
decomposed into $\pi_k(0)$ and $\pi_k(1)$.

Let $n$ be a positive integer; suppose it is large.
The sequence $(l_k)_{k \geq 1}$ is increasing, so there is a unique
positive integer $k$ such that $l_{k-1} \leq n < l_k$. Consequently,
all factors of length $n$ of $\mathbf{w}_{\pi}$ belong to ${\rm Fac}
\left( \pi_1 \cdots \pi_k \left( \{0,1\}^2 \right) \right)$. From what
precedes, there is a unique word $v$ in ${\rm
Fac}\left(\pi_k\left(\{0,1\}^2\right)\right) \subset {\rm
Fac}\left(\mathbf{w}^{(k)}\right)$ such that $u \in {\rm Fac}(\pi_1
\cdots \pi_{k-1}(v))$ and any word $v'$ over $\{0,1\}$ such that $u \in
{\rm Fac} \left( \pi_1 \cdots \pi_{k-1}(v') \right)$ contains $v$ as a
factor.

By the uniqueness of $v$, the number of return words to $u$ in
$\mathbf{w}_{\pi}$ is at least equal to the number of return words to
$v$ in $\mathbf{w}^{(k)}$ (some return words might also occur in $\pi_1
\cdots \pi_{k-1}(v)$), so we only have to show that the number of return
words to $v$ in $\mathbf{w}_k$ is at least linear in $k$. This will
prove the result since $k$ increases with $n$.

First, if $|v| \geq 7$, we have seen that there is a unique word $x \in
\{0,1,00,01,10,11\}$ such that $v \in {\rm Fac}(\pi_k(x))$ and such
that if $v \in {\rm Fac}(\pi_k(y))$, then $x \in {\rm Fac}(y)$. The
number of return words to $v$ in $\mathbf{w}^{(k)}$ is at least equal
to the number of return words to $x$ in $\mathbf{w}^{(k+1)}$, and 
the reader can verify that it is at least linear in $k$.

Let us suppose that $|v| < 7$ and that the factor $000$
occurs in $v$ (the case $111 \in {\rm Fac}(v)$ is similar). Then, from
the form of $\pi_k$, the word
$v$ only occurs in $\mathbf{w}^{(k)}$ as factor of
$\pi_k(1)$. The number of return words to $v$ in $\mathbf{w}^{(k)}$ is
then at least equal to the number of return words to $1$ in
$\mathbf{w}^{(k+1)}$, and the reader can verify that it is at least
linear in $k$.

Now suppose that neither $000$ nor $111$ occur in $v$ (still with $|v|
< 7$). Since the number of return words to a factor is the same as the
number of return words to the smallest bispecial factor containing it,
we only have to count the number of return words to bispecial factors
of $\mathbf{w}^{(k)}$ that are smaller than $7$ and that do not contain
either $000$ or $111$ as factors. The reader can now
verify that these are given by
\[
	\left\{	0,1,00,01,10,11,010,101,0101,1010,01010,01011,11010,10101,010101,101010	\right\}.
\]
The bispecial factors $01010$, $10101$, $010101$ and $101010$ only
occur in $\mathbf{w}^{(k)}$ as factors of $\pi_k(01)$ and $\pi_k(01)$
but are neither factors of $\pi_k(0)$ nor of $\pi_k(1)$. Since the
number of words filling the gaps between occurrences of $01$ and $10$
in $\mathbf{w}^{(k+1)}$ is linear in $k$, these bispecial factors have
a number of return words that is linear in $k$, too.

The reader can now verify that the other bispecial factors have a number of return words in $\mathbf{w}^{(k)}$ which is linear in $k$ (each return word containing a different highest power of $0$ or of $1$ depending on the bispecial factor). This completes the proof.
\end{proof}
\end{example}

To end with return words, let us observe that it is possible to build
sequences whose complexity is not linear and in which infinitely
many factors have a bounded number of return words. Indeed, the
sequence $\gamma^{\omega}(0)$ (see Example~\mbox{\ref{ex: morse+n^2}})
has quadratic complexity and any factor $\gamma^n(1)$ admits two
return words.  After the last observation, it seems difficult to
characterize sequences with linear complexity using return words.
Nevertheless, the next interesting question is open.

\begin{question}
Let $\mathbf{w}$ be a sequence such that, for some integer $K$, all factors of $\mathbf{w}$ have at most $K$ return words. Is it true that $\mathbf{w}$ is $S$-adic for some suitable {set} $S$ and has linear complexity?
\end{question}


\subsection{Number of distinct high powers}
\label{subsection: distinct powers}

As already mentioned, it is known that the factor complexity of
$k$-power-free pure morphic sequences grows at most like $n \log n$. In
this section, we explore links between bounding the number of distinct
exponents of factors instead of the maximal exponent of factors and the
factor complexity.

Let us introduce the following notation: given a language $L$ and a
word $u = u_1 \cdots u_{|u|} \in L$, ${\rm Pow}(u, L)$ is the set of
all non-negative integers $i$ such that there exist words $p$ and
$s$ such that $pu^i s$ belongs to $L$, $|p| \leq |u|$, $|s|\leq |u|$,
$p$ is not a suffix of $u$, and $s$ is not a prefix of $u$.

It is certainly well known that for any Sturmian sequence $\mathbf{w}$ and any factor $u$ of $\mathbf{w}$, 
we have ${\rm Card}\left({\rm Pow}(u, {\rm Fac}(\mathbf{w}_\pi))\right) = \{1,2\}$. 
Indeed if ${\rm Card}\left({\rm Pow}(u, {\rm Fac}(\mathbf{w}_\pi))\right) \geq 3$ for a factor $u$ of a Sturmian sequence $\mathbf{w}$, 
any factor of length $|u|$ not in ${\rm Fac}(u^\omega)$ (such a factor exists since $p_{\mathbf{w}}(|u|) = |u|+1)$) would have at least $3$ return words, contradicting the result of Vuillon \cite{Vuillon_sturmian} 
that all factors of a Sturmian sequence have two return words.

\begin{example}[Example~\ref{ex: plein de mots de retours} continued]
With the notation of previous section, we have ${\rm Pow}(\pi_1\cdots \pi_n(0), {\rm Fac}(\mathbf{w}_\pi)) = \{3^0, 3^1, \ldots, 3^n\}$, which proves the existence of an $S$-adic sequence with at most linear complexity that has factors with an unbounded number of distinct exponents.
\end{example}

\begin{example}[Example~\ref{ex: morse+n^2} continued]
The previous phenomenon also holds for $S$-adic sequences that do not have 
linear complexity.
Indeed, this is the case of the $S$-adic sequence considered in Proposition~\ref{prop: morse+n^2} when the sequence $(k_n)_{n \in \mathbb{N}}$ is unbounded, as one can observe that
\[
	{\rm Pow}(\gamma^{k_0} \mu \gamma^{k_1} \mu \gamma^{k_2} \mu \cdots \gamma^{k_n} \mu(1), {\rm Fac}(\mathbf{w}_{\gamma,\mu})) = \{1, 2, \ldots, k_{n+1}+2\}.
\]
\end{example}

It seems difficult from the previous discussion to get an $S$-adic characterization of sequences with linear complexity using the number of distinct powers of their factors.
Nevertheless, inspired by the word $\mathbf{w}_{\gamma,\mu}$,
Corollary~\ref{cor: puissances}  
provides a new criterion
for proving
that a sequence does not have linear complexity. Recall that a 
nonempty word
$u$ is \textit{primitive} if it is not a power of a smaller word $v$,
i.e., there is no integer $k \geq 2$ such that $u = v^k$.

\begin{lemma}
\label{lemme: puissances}
Let $\mathbf{w}$ be a recurrent sequence over $A$. If $u \in {\rm Fac}(\mathbf{w})$ is a primitive word such that there exist positive integers $k$ and $i < k/2$ with $k-i \in {\rm Pow}(u,{\rm Fac}(\mathbf{w}))$, then there is a subset $F_i$ of factors of length $k|u|$ of $\mathbf{w}$ such that ${\rm Card}(F_i) = i|u|$. Moreover, for $i \neq i'$ we have $F_i \cap F_{i'} = \emptyset$. 
\end{lemma}

Before proving the result, let us recall the following classical result
(see, for instance,
\cite[Prop.\ 1.3.2]{Lothaire1983}).

\begin{proposition}
\label{prop: xy yx}
If $x$ and $y$ are two nonempty words such that $xy = yx$,
then there is a word $v$ shorter than or the same length as $x$ and $y$
such that $x = v^n$ and $y = v^m$ for some positive integers $n$ and $m$.
\end{proposition}

\begin{proof} (of Lemma~\ref{lemme: puissances})
By hypothesis the word $u^{k-i}$ is a factor of $\mathbf{w}$ and occurs
infinitely many times in $\mathbf{w}$. Let us study the return words to
it in $\mathbf{w}$.

Since $u$ is a primitive word, a return word $r$ to it is either $u$ or has length $|r| > (k-i)|u|$. Indeed, if not, one of the following holds:
\begin{enumerate}
	\item $|r| = j|u|$ with $2 \leq j \leq k-i$; in this case, we have $r = u^j$ which is not a return word to $u$ because it contains more than two occurrences of $u$;
	\item $|r| < (k-i)|u|$ and $|r|$ is not a multiple of $|u|$; in this case, there is a nonempty word $u'$ smaller than $u$ such that $u' u = u u'$ and, by Proposition~\ref{prop: xy yx}, $u$ is not a primitive word.
\end{enumerate}
 
Now, since $k-i$ belongs to ${\rm Pow}(u,{\rm Fac}(\mathbf{w}))$ and $\mathbf{w}$ is recurrent, there are two words $p_i$ and $s_i$ such that $p_i u^{k-i} s_i$ belongs to ${\rm Fac}(\mathbf{w})$, $|p_i| \leq |u|$, $|s_i| \leq |u|$ and
$u$ does not admit $p_i$ as a suffix or $s_i$ as a prefix.
Thus, from what precedes, $p_i$ is a suffix of a return word $r_i$ to $u^{k-i}$ with $|r_i| > (k-i)|u|$ and such that $r_i u^{k-i} s_i$ is a factor of the recurrent word $\mathbf{w}$.

By hypothesis, we have $k-i > k/2$, so we get
\[
	|r_i u^{k-i}| > k |u|.
\]

Let $v_i$ denote the suffix of length $k|u|$ of $r_i u^{k-i}$ and let $x_i$ denote a factor of $\mathbf{w}$ of length $(k+i)|u|$ that admits $v_i s_i$ as a prefix. For a given word $w = w_1 \cdots w_{|w|}$, we let $w[r:s]$ denote its factor $w_r \cdots w_{s-1}$. By definition of return words, the word $u^{k-i}$ occurs only once in $v_i$. Thus all the words 
\[
	x_i[\ell:\ell+k|u|], \quad \ell \in \{1,2,\dots,i|u|\}, 
\]
are different. We take $F_i = \{x_i[\ell:\ell+k|u|] \mid \ell \in \{1,2,\dots,i|u|\}\}$.


Let us show that if $i$ and $j$ are such that $1 \leq i < j < k/2$, then $F_i \cap F_j = \emptyset$, i.e., all words 
\begin{eqnarray*}
	x_i[\ell : \ell + k |u|], 		& \ell \in \{1,2,\dots,i|u|\} \\
	x_j[m : m + k |u|],		 		& m \in \{1,2,\dots,j|u|\}
\end{eqnarray*}
are distinct. Suppose that on the contrary
there are some integers $\ell \in \{1,2,\dots,i|u|\}$ and $m \in \{1,2,\dots,j|u|\}$ such that
\[
	x_i[\ell:\ell+k|u|] = x_j[m:m+k|u|] = X. 
\]
Since $\ell \leq i|u|$ and $m \leq j|u|$, there are some words $\alpha$, $\beta$, $\gamma$ and $\delta$ such that 
\[
	X = \alpha u^{k-i} \beta = \gamma u^{k-j} \delta.
\]
We have $|\alpha|>|\gamma|$; otherwise $u^{k-j}$ would occur twice in $v_j$. 
Let us show that we also have $|\alpha| < |\gamma| + (k-j)|u|-|u|$. As $k - i > k - j > k/2$, we have
\[
	(k-i)|u| \geq (k-j+1)|u| > k|u|/2+|u|.
\]
Thus, if $|\alpha| \geq |\gamma| + (k-j)|u|-|u|$, we have 
\begin{eqnarray*}
	|\alpha| + (k-i)|u|  &\geq	& |\gamma| + (k-j)|u|-|u| + (k-j+1)|u|	\\
						& >		& |\gamma| + k |u|,
\end{eqnarray*}
which is a contradiction because $|\alpha u^{k-i}\beta|=k|u|$.

We have just proved that 
\[
	|\gamma| < |\alpha| < |\gamma| + (k-j)|u|-|u| = |\gamma u^{k-j-1}|.
\]
This implies that, if $p$ is the prefix of length $(|\alpha|-|\gamma|) \mod |u|$ of $u$, we have $up = pu$. Since $|\alpha|-|\gamma| \neq 0 \mod |u|$ (otherwise $s_j$ would be a prefix of $u$), Proposition~\ref{prop: xy yx} implies that $u$ is not primitive, a contradiction. Thus we have $F_i \cap F_j = \emptyset$.
\end{proof}

\begin{corollary}
\label{cor: puissances}
Let $\mathbf{w}$ be a recurrent sequence over $A$. If
\begin{equation}
\label{eq: critere puissances}
	\sup_{\begin{subarray}{c} 
	u \in {\rm Fac}(\mathbf{w}), \\ 
	u \ \text{primitive word},	\\
	k \geq 1 
	\end{subarray}}
	\sum_{\begin{subarray}{c} 
	0 < i < k/2,	\\
	k-i \in {\rm Pow}(u,{\rm Fac}(\mathbf{w})) \\  
	\end{subarray}}
	\frac{i}{k}
	=
	+\infty,
\end{equation}
then $\mathbf{w}$ does not have linear complexity.
\end{corollary}

\begin{proof}
Let $u$ be a primitive word in ${\rm Fac}(\mathbf{w})$ and let $i$ and $k$ be integers as in Lemma~\ref{lemme: puissances}. This lemma permits us
to obtain a lower bound on the number of factors of length $k|u|$.
Indeed, we immediately deduce that
\[
	p_{\mathbf{w}}(k |u|) 
	\geq 
	\sum_{\begin{subarray}{c} 
	0 < i < k/2, 	\\
	k- i \in {\rm Pow}(u,{\rm Fac}(\mathbf{w}))  
	\end{subarray}}
	i |u|
	=
	|u|
	\sum_{\begin{subarray}{c} 
	0 < i < k/2, 	\\
	k- i \in {\rm Pow}(u,{\rm Fac}(\mathbf{w}))  
	\end{subarray}}
	i.	
\]
But, as we have
\[
	\sup_{\begin{subarray}{c} 
	u \in {\rm Fac}(\mathbf{w}), \\ 
	u \ \text{primitive word},	\\
	k \geq 1 
	\end{subarray}}
	\frac{1}{k}
	\sum_{\begin{subarray}{c} 
	0 < i < k/2,	\\
	k-i \in {\rm Pow}(u,{\rm Fac}(\mathbf{w})) \\  
	\end{subarray}}
	i	
	=
	+\infty,
\]
the sequence $\mathbf{w}$ does not have linear complexity.
\end{proof}

\begin{remark}
The hypothesis of primitivity of the words $u$ in previous results
cannot be avoided. Indeed, consider the fixed point $\mathbf{w} =
\sigma^{\omega}(0)$ with $\sigma(0)=010$ and $\sigma(1)=111$. The
sequence $(1^{3n})_{n \in \mathbb{N}}$ satisfies~\eqref{eq: critere
puissances} (without primitivity) but $p_{\mathbf{w}}(n) = 2n-1$ for
all $n \geq 2$.
\end{remark}

The next example shows that the converse of Corollary~\ref{cor:
puissances} does not hold.

\begin{example}
\label{example: peu de puissance mais complexité expo}
It is well known that the Thue-Morse sequence $\mathbf{t} \in \{0,1\}^{\mathbb{N}}$ is cubefree~\cite{Thue1912}, i.e., it does not contain any factor of the
form $xxx$. 
It is also strongly recurrent~\cite{Salimov}, which means that the direct product of it with any uniformly recurrent sequence is uniformly recurrent.
Let $\mathbf{w}$ be a uniformly recurrent sequence over $\{0,1\}$ with exponential complexity (such a word exists from Theorem~\ref{thm: grillenberger}).
The direct product $\mathbf{t} \times \mathbf{w}$ is then a uniformly recurrent sequence over the four-letter alphabet $\{(0,0),(0,1),(1,0),(1,1)\}$ which has exponential complexity and which is cubefree (because so is $\mathbf{t}$).
Thus we have
\[
	\sup_{\begin{subarray}{c} 
	u \in {\rm Fac}(\mathbf{t} \times \mathbf{w}), \\ 
	u \ \text{primitive word},	\\
	k \geq 1 
	\end{subarray}}
	\sum_{\begin{subarray}{c} 
	0 < i < k/2,	\\
	k-i \in {\rm Pow}(u,{\rm Fac}(\mathbf{t} \times \mathbf{w})) \\  
	\end{subarray}}
	\frac{i}{k}
	= 0.
\]
\end{example}

Despite the fact that the
converse of Corollary~\ref{cor: puissances} does not hold,
Corollary~\ref{cor: exemple avec puissances et faible complexite} below
provides a family of sequences satisfying~\eqref{eq: critere
puissances} and whose complexities are very close to linear.  First,
we need the following result, which is obtained by a simple
adaptation of Durand's result~\cite[Prop.\ 2.1]{Durand_corrigentum}
(which is equivalent to Proposition~\ref{prop: durand longueur
comparable S-adic} on page~\pageref{prop: durand longueur comparable
S-adic}).


\begin{proposition}
\label{prop: croissance controlee}
Let $\mathbf{w}$ be an everywhere-growing $S$-adic sequence whose
directive word is $(\sigma_n)_{n \in \mathbb{N}}$ with $\sigma_n:
A_{n+1}^* \to A_n^*$ and $A_0$ the alphabet of $\mathbf{w}$. If there
is a constant $K$ such that for all $n$ we have ${\rm Card}(A_n) \leq K$, and
if there is a function $D: \mathbb{N} \to \mathbb{R}$ such that for all
$n$ and all $a \in A_{n+2}$, $b \in A_{n+1}$ we have
\begin{equation}
\label{eq: cond croissance controlee}
	|\sigma_0 \cdots \sigma_{n+1}(a)| \leq D(n) |\sigma_0 \cdots \sigma_n(b)|,
\end{equation}
then for all $m$, $p_{\mathbf{w}}(m) \leq K^2 D(n(m)) m$,
where $n(m)$ is the greatest integer such that 
\[
	\min_{a \in A_{n(m)+1}} |\sigma_0 \cdots \sigma_{n(m)}(a)| \leq m.
\]
\end{proposition} 

\begin{proof}
Let $m \geq 1$. Since the sequence $\left(\inf_{a \in A_{k+1}} |\sigma_0 \cdots \sigma_k(a)|\right)_{k \in \mathbb{N}}$ is non-decreasing and tends to $+\infty$, there is a greatest integer $n(m)$ such that
\[
	\inf_{a \in A_{n(m)+1}} |\sigma_0 \cdots \sigma_{n(m)}(a)|  \leq m \leq \inf_{a \in A_{n(m)+2}} |\sigma_0 \cdots \sigma_{n(m)+1}(a)|.
\]
Consequently, for any word $u$ in ${\rm Fac}_m(\mathbf{w})$, there exist 
letters $b$ and $c$ in $A_{n(m)+2}$ and a positive integer $i \leq |\sigma_0 \cdots \sigma_{n(m)+1}(b)|$ such that $u = \sigma_0 \cdots \sigma_{n(m)+1}(bc)[i:i+m]$. It comes
\begin{eqnarray*}
	p_{\mathbf{w}}(m) 	&	\leq	& K^2 \sup_{a \in A_{n(m)+2}} |\sigma_0 \cdots \sigma_{n(m)+1}(a)|	\\
						&	\leq	& K^2 D(n(m)) \inf_{a \in A_{n(m)+1}} |\sigma_0 \cdots \sigma_{n(m)}(a)|	\\
						&	\leq 	& K^2 D(n(m)) m.
\end{eqnarray*}
\end{proof}

The idea of the next result is to build a directive word $(\sigma_n)_{n
\in \mathbb{N}}$ satisfying~\eqref{eq: cond croissance controlee} with
slowly increasing functions $D(n)$ and $n(m)$ while producing more and
more powers with morphisms $\sigma_n$.

\begin{corollary}
\label{cor: exemple avec puissances et faible complexite}
Let $(\phi (n))_{n\geq 0}$ be a non-decreasing sequence of integers greater or equal to $2$ such that $\lim_n \phi (n) = +\infty $.
There exists a non-periodic sequence $\mathbf{w} \in \{ 0,1 \}^\mathbb{N}$ such that:
\begin{enumerate}[i.]
	\item 	$\mathbf{w}$ satisfies~\eqref{eq: critere puissances} in Corollary~\ref{cor: puissances};
	\item	$p_\mathbf{w} (n) \leq 4 \phi (\log_2 (n)) n$ for all $n$;
	\item	$p_\mathbf{w} (n) \leq 8 n$ for infinitely many $n$.
\end{enumerate}
\end{corollary}

\begin{proof}
Let $\mu$ be the Thue-Morse morphism (see Example~\ref{ex: morse+n^2} on Page~\pageref{ex: morse+n^2}).
For all integers $n \geq 2$, let $\tau_n$ be the uniform morphism over $\{0,1\}$ defined by:
\[
	\tau_n :	\begin{cases}
					0 \mapsto 0 u 0	\\
					1 \mapsto 1 v 1
				\end{cases},
\]
where $u$ and $v$ are the prefixes of length $n-2$ of $\prod_{i \geq 1} 1^i0$ and $\prod_{i \geq 1} 0^i1$ respectively. For instance, we have
\[
	\tau_9 :	\begin{cases}
					0 \mapsto 010110110	\\
					1 \mapsto 101001001
				\end{cases}
	\qquad
	\tau_{10} :	\begin{cases}
						0 \mapsto 0101101110	\\
						1 \mapsto 1010010001
					\end{cases}.	
\] 

Let $(\sigma_n)_{n \in \mathbb{N}}$ be the sequence of morphisms defined, for all $n \geq 0$, by
\[
	\sigma_{2n} = \mu \qquad \text{and} \qquad \sigma_{2n+1} = \tau_{\phi (n)}.
\]

By construction, the sequence $\mathbf{w} = \lim_{n \to +\infty}
\sigma_0 \cdots \sigma_n(0)$ satisfies the hypothesis of
Corollary~\ref{cor: puissances}, so it does not have linear
complexity.

Let us give a general upper bound for $p_{\mathbf{w}}(m)$, using Proposition~\ref{prop: croissance controlee} and its terminology $D(n)$ and $n(m)$.
For all $n$, we have $|\sigma_{n+1}(0)| = |\sigma_{n+1}(1)| \leq \phi(\left\lfloor n/2 \right\rfloor) \leq \phi(n)$. Thus we can choose $D(n) \leq \phi(n)$. 
For all $m$ we have $|\sigma_0 \cdots \sigma_m(0)| = |\sigma_0 \cdots \sigma_m(1)| \geq 2^m$. Thus $n(m) \leq \log_2(m)$ and we obtain
\[
	p_{\mathbf{w}}(m) \leq 4 \phi(\log_2(m))m.
\]

Now let us prove that $p_{\mathbf{w}}(m) \leq 8 m$ for infinitely many $m$.
Consider $m = |\sigma_0 \sigma_1 \cdots \sigma_{2k+1}(0)|$. We have $n(m)= 2k+1$ and we can set $D(2k) = |\sigma_{2k}(0)|=|\mu(0)| = 2$; hence
\[
	p_\mathbf{w} (m) \leq 8 m.
\]
\end{proof}

\section{Beyond linearity}
\label{section beyond lin}

Until now, we have provided several examples showing that various
natural approaches to characterize $S$-adic sequences that have
linear complexity do not appear to be promising. To conclude this
paper, we raise a new problem related to $S$-adicity and, more
precisely, to everywhere-growing $S$-adic sequences.

For pure morphic sequences, the complexity function can have only 5
asymptotic behaviors and only depends on the growth rate of images (see
Theorem~\ref{thm: pansiot}). For $S$-adic sequences, we have seen in
Section~\ref{subsection S-adic} that things are more complicated.
However, Ferenczi~\cite{Ferenczi} (see
also~\cite{Leroy,Leroy-Richomme}) proved that any uniformly recurrent
sequence with linear complexity is everywhere-growing $S$-adic with
$S$ finite. This is a kind of generalization of the third point of
Theorem~\ref{thm: pansiot}. Moreover, one can check that all examples
considered in previous sections (and more generally all $S$-adic
representations of well-known families of sequences such as codings of
rotations, codings of interval exchanges, etc.) are everywhere-growing
with $S$ finite.  It is also interesting to note that for pure morphic
sequences, the class of highest complexity $\Theta(n^2)$ can be reached
only by morphisms with bounded letters (Theorem~\ref{thm:
pansiot}).  A similar phenomenon occurs for $S$-adic sequences. Indeed,
Cassaigne's constructions (Proposition~\ref{prop:Cassaigne adique})
allow building $S$-adic sequences with arbitrarily high complexity and
they admit several bounded letters.  Consequently, the fact that the
length of all images tends to infinity with $n$ seems to be important
to get a \textit{reasonably low complexity}.  This is confirmed by the
following two lemmas. The first one can be found in a paper written by Boyle and Handelman~\cite{Bezuglyi} and certainly elsewhere. 
We let denote $h(\mathbf{w})$ the
entropy of the sequence $\mathbf{w}$ (see Section~\ref{subsection
S-adic}).

\begin{lemma}
\label{lemma:majentropy}
Let $L$ be a set of $m$ finite words of length at least $l$ and at most $k$.
Let $\mathbf{w}$ be an infinite concatenation of elements of $L$. 
Then 
$$
	p_\mathbf{w}(n) \leq k m^{2+\frac{n}{l}} \hbox{ and } h(\mathbf{w}) \leq \frac{\log m}{l} .
$$
\end{lemma}

As a corollary we obtain the following lemma whose conclusion was
certainly known in the 1970's in ergodic theory, for instance to prove
that measure-theoretical dynamical systems of bounded rank have entropy
zero (see \cite{Boyle&Handelman}).

\begin{lemma}
Let $\mathbf{w}$ be an $S$-adic sequence whose directive word is $(\sigma_n)_{n \in \mathbb{N}}$ with $\sigma_n: A_{n+1}^* \to A_n^*$ and $A_0$ the alphabet of $\mathbf{w}$. 
Then, for all $n$ such that $\min_{a\in A_{n+1}} |\sigma_0 \cdots \sigma_n(a)|\not = 0$,
\[
	h(\mathbf{w}) \leq \frac{\log \left({\rm Card}(A_{n+1})\right)}{\min_{a\in A_{n+1}} |\sigma_0 \cdots \sigma_n(a)|}.
\]
Thus, if $({\rm Card}(A_n))_{n \in \mathbb{N}}$ is bounded and $(\min_{a\in A_{n+1}} |\sigma_0 \cdots \sigma_n(a)|)_{n \in \mathbb{N}}$ tends to infinity, then $h(\mathbf{w})=0$.
\end{lemma}
\begin{remark}
The previous lemma shows that to build an $S$-adic sequence with a very high complexity (i.e., with positive entropy), either we need bounded letters,
or we need the set $S$ to be infinite and the alphabets $A_{n+1}$ must
grow exponentially in the minimal length of the images $\sigma_0 \cdots
\sigma_n(a)$.

Moreover, the converse of previous lemma is not true: there exist sequences of zero entropy without $S$-adic representation satisfying the hypothesis. Indeed, as shown by Williams \cite{Williams:1984} (also see \cite{Gjerde:2000}) there exist (Toeplitz) sequences $x$ with zero entropy whose generated subshift $(X,S)$ has infinitely many ergodic measures.
It is part of the folklore of ergodic theory that, in our context and for uniformly recurrent sequences, when
$(|A_n|)_n$ is bounded by some constant $k$ and $(\min_{a\in A_{n}} |\sigma_0 \cdots \sigma_n(a)|)_n$ tends to infinity,
then the subshift generated by the $S$-adic sequence has at
most $k$ ergodic measures.
Thus $x$ has zero entropy but does not have an $S$-adic representation with $(|A_n|)_n$ bounded and $(\min_{a\in A_{n}} |\sigma_0 \cdots \sigma_n(a)|)_n$ going to infinity.
\end{remark}

Observe that, given an $S$-adic sequence $\mathbf{w}$, the everywhere-growing property is not a necessary condition for $\mathbf{w}$ to have low complexity. Indeed, Cassaigne's constructions also hold for sequences with low complexity. One can also recall the \textit{Chacon substitution} $\varrho$ defined by $\varrho(0)=0010$ and $\varrho(1)=1$ whose fixed point $\varrho^{\omega}(0)$ has complexity $p(n)=2n-1$ for all $n$ (see~\cite{chacon}). However, \textit{the existence} of an everywhere-growing $S'$-adic representation of $\mathbf{w}$ might be necessary (this is the case for the Chacon substitution and for any uniformly recurrent sequence with linear complexity). 

That property is neither a sufficient condition since the sequence
$\mathbf{w}_{\gamma,E}$ of Example~\ref{ex: morse+n^2} satisfies it and
does not always have linear complexity. However, it seems natural
to look for Pansiot-like results.

\begin{question}
Let $\mathbf{w}$ be an everywhere-growing $S$-adic sequence directed by $(\sigma_n)_{n \in \mathbb{N}}$ such that the alphabets $A_n$ have bounded cardinality. 
How can the ratio\footnote{Considering only the growth rate of $\min_{a \in A_{n+1}} |\sigma_0 \cdots \sigma_n(a)|$ is not enough since it would suffices to add occurrences of the identity morphism in $(\sigma_n)_{n \in \mathbb{N}}$ to change this growth rate.} $\max_{a,b \in A_{n+1}} \frac{|\sigma_0 \cdots \sigma_n(a)|}{|\sigma_0 \cdots \sigma_n(b)|}$ influence $p_{\mathbf{w}}$? 
\end{question}

This question seems to be a new and non-trivial problem.
Proposition~\ref{prop: S-adic bounded by n log n} below provides a
partial answer to this question. Indeed, it deals with
\textit{expansive} $S$-adic sequences, i.e., with $S$-adic sequences
such that for all morphisms $\sigma$ in $S$ and all letters $a$, we
have $|\sigma(a)| \geq 2$. Leroy's proof~\cite{Leroy} involves
techniques similar to those used by Ehrenfeucht, Lee, and
Rozenberg~\cite{D0L} for D0L systems.

\begin{proposition}
\label{prop: S-adic bounded by n log n}
If $\mathbf{w}$ is an expansive $S$-adic sequence with ${\rm Card}(S)< +\infty$, then $p_{\mathbf{w}}(n) \in \mathcal{O}(n \log n)$.
\end{proposition}

The next example shows that the bound of Proposition~\ref{prop: S-adic
bounded by n log n} is the best one we can obtain.

\begin{example}
\label{example: complexity n log n}
Let $\vartheta$ be the morphism
\[
	\vartheta :	\begin{cases}
					0 \mapsto 0120	\\
					1 \mapsto 11	\\
					2 \mapsto 222
				\end{cases}
\]
and consider its fixed point $\mathbf{w}_{\vartheta}=\vartheta^{\omega}(0)$.
It can be seen as an expansive $\{\vartheta\}$-adic sequence and, by Theorem~\ref{thm: pansiot}, we have that $p_{\mathbf{w}_{\vartheta}}(n) \in \Theta(n \log n)$. 
\end{example}

\section{Acknowledgments}

Many thanks to the two referees for their valuable comments.


\def\cprime{$'$}
\begin{thebibliography}{ELR75}

\bibitem[AB07]{Adamczewski}
B.~Adamczewski and Y.~Bugeaud,
\newblock On the complexity of algebraic numbers {I}: {E}xpansions in integer
  bases,
\newblock {\em Ann. Math.} \textbf{165} (2007), 547--565.

\bibitem[AB11]{Adamczewski2}
B.~Adamczewski and Y.~Bugeaud,
\newblock Nombres r\'eels de complexit\'e sous-lin\'eaire: mesures d'irrationalit\'e et de transcendance,
\newblock {\em J. Reine Angew. Math.} \textbf{658} (2011), 65--98.

\bibitem[Abe03]{Aberkane}
A.~Aberkane,
\newblock Words whose complexity satisfies {$\lim\frac{p(n)}{n}=1$},
\newblock {\em Theoret. Comput. Sci.} \textbf{307} (2003), 31--46.

\bibitem[All94]{allouche_survey}
J.-P.~Allouche,
\newblock Sur la complexit\'e des suites infinies,
\newblock {\em Bull. Belg. Math. Soc. Simon Stevin} \textbf{1} (1994), 133--143.

\bibitem[AR91]{Arnoux-Rauzy}
P.~Arnoux and G.~Rauzy,
\newblock Repr\'esentation g\'eom\'etrique de suites de complexit\'e {$2n+1$},
\newblock {\em Bull. Soc. Math. France} \textbf{119} (1991), 199--215.

\bibitem[AZ98]{AlloucheZamboni98}
J. P.~Allouche and L. Q.~Zamboni,
\newblock Algebraic irrational binary numbers cannot be fixed points of non-trivial constant length or primitive morphisms,
\newblock {\em J. Number Theory} \textbf{69} (1998), 119--124.

\bibitem[Ber80]{Berstel1980}
J.~Berstel,
\newblock Mots sans carr\'e et morphismes it\'er\'es,
\newblock {\em Discrete Math.} \textbf{29} (1980), 235--244.

\bibitem[BH94]{Bezuglyi}
M.~Boyle and D.~Handelman,
\newblock Entropy versus orbit equivalence for minimal homeomorphisms, 
\newblock {\em Pacific J. Math.} \textbf{164} (1994), 1--13.

\bibitem[BHZ06]{BHZ}
V.~Berth\'e, C.~Holton, L. Q.~Zamboni, 
\newblock Initial powers of Sturmian words,
\newblock {\em Acta Arith.} \textbf{122} (2006), 315--347.

\bibitem[BKMS]{Boyle&Handelman}
S.~Bezuglyi, J.~Kwiatkowski, K.~Medynets, and B.~Solomyak,
\newblock Finite rank Bratteli diagrams: structure of invariant measures, 
\newblock Preprint.  Available at \url{http://arxiv.org/abs/1003.2816}.

\bibitem[Bos84]{Boshernitzan84}
M.~Boshernitzan,
\newblock 
A unique ergodicity of minimal symbolic flows with linear block growth,
\newblock {\em J. Analyse Math.}, \textbf{44} (1984/85), 77--96.

\bibitem[Bos92]{Boshernitzan92}
M.~Boshernitzan,
\newblock A condition for unique ergodicity of minimal symbolic flows,
\newblock {\em Ergodic Theory Dynam. Systems}, \textbf{12} (1992), 425--428.

\bibitem[BPS08]{Balkova-Pelantova-Steiner}
L.~Balkov{\'a}, E.~Pelantov{\'a}, and W.~Steiner,
\newblock Sequences with constant number of return words,
\newblock {\em Monatsh. Math.} \textbf{155} (2008), 251--263.

\bibitem[BR10]{CANT}
V.~Berth\'{e} and M.~Rigo, eds.,
\newblock {\em Combinatorics, Automata and Number Theory}, Vol.\ 135 of {\em
  Encyclopedia of Mathematics and its Applications},
\newblock Cambridge University Press, 2010.

\bibitem[Cas96]{Cassaigne_big_thm}
J.~Cassaigne,
\newblock Special factors of sequences with linear subword complexity,
\newblock In {\em Developments in Language Theory, {II}},
  World Sci. Publ., 1996, pp.\ 25--34.

\bibitem[Cas97]{Cassaigne_resume}
J.~Cassaigne,
\newblock Complexit\'e et facteurs sp\'eciaux,
\newblock {\em Bull. Belg. Math. Soc. Simon Stevin} \textbf{4} (1997), 67--88.

\bibitem[Cas03]{Cassaigne_intermediate}
J.~Cassaigne,
\newblock Constructing infinite words of intermediate complexity,
\newblock in {\em Developments in Language Theory}, {\em Lect.
  Notes in Comput. Sci.}, Vol.\ 2450, Springer, 2003, pp.\ 173--184.

\bibitem[CN03]{Cassaigne-Nicolas}
J.~Cassaigne and F.~Nicolas,
\newblock Quelques propri\'et\'es des mots substitutifs,
\newblock {\em Bull. Belg. Math. Soc. Simon Stevin} \textbf{10} (2003), 661--676.

\bibitem[Cob68]{Cobham_hartmanis}
A.~Cobham,
\newblock On the {H}artmanis-{S}tearns problem for a class of tag machines,
\newblock in {\em Proc. of 9th Annual Symposium on Switching and
  Automata Theory}, 
  IEEE Computer Society, 1968, pp.\ 51--60.

\bibitem[CS01]{CanteriniSiegel01}
V.~Canterini and A.~Siegel,
\newblock Geometric representation of substitutions of {P}isot type,
\newblock {\em Trans. Amer. Math. Soc.} \textbf{353} (2001), 5121--5144.

\bibitem[Dev08]{Deviatov}
R.~Deviatov,
\newblock On subword complexity of morphic sequences,
\newblock in {\em Computer Science -- Theory and Applications}, 
  {\em Lect. Notes in Comput. Sci.}, Vol.\ 5010, Springer, 2008, pp.\ 146--157. 

\bibitem[DL06]{Damanik-Lenz}
D.~Damanik and D.~Lenz,
\newblock Substitution dynamical systems: characterization of linear repetitivity and applications,
\newblock {\em J. Math. Anal. Appl.} \textbf{321} (2006), 766--780.

\bibitem[Dur]{Durand_preprint}
F.~Durand,
\newblock Decidability of uniform recurrence of morphic sequences,
\newblock {\em Internat. J. Found. Comput. Sci.}, to appear.

\bibitem[Dur98]{Durand_UR}
F.~Durand, 
\newblock A characterization of substitutive sequences using return words,
\newblock {\em Discrete Math.} \textbf{179} (1998), 89--101.

\bibitem[Dur00]{Durand_LR}
F.~Durand,
\newblock Linearly recurrent subshifts have a finite number of non-periodic
  subshift factors,
\newblock {\em Ergodic Theory Dynam. Systems} \textbf{20} (2000), 1061--1078.

\bibitem[Dur03]{Durand_corrigentum}
F.~Durand,
\newblock Corrigendum and addendum to: ``{L}inearly recurrent subshifts have a
  finite number of non-periodic subshift factors'',
\newblock {\em Ergodic Theory Dynam. Systems} \textbf{23} (2003), 663--669.

\bibitem[ELR75]{D0L}
A.~Ehrenfeucht, K.~P.~Lee, and G.~Rozenberg,
\newblock Subword complexities of various classes of deterministic
  developmental languages without interactions,
\newblock {\em Theoret. Comput. Sci.} \textbf{1} (1975), 59--75.

\bibitem[ER83]{D0L_m-free}
A.~Ehrenfeucht and G.~Rozenberg,
\newblock On the subword complexity of {$m$}-free {D0L} languages,
\newblock {\em Inform. Process. Lett.} \textbf{17} (1983), 121--124.

\bibitem[Fer95]{chacon}
S.~Ferenczi,
\newblock Les transformations de {C}hacon: combinatoire, structure
  g\'eom\'etrique, lien avec les syst\`emes de complexit\'e {$2n+1$},
\newblock {\em Bull. Soc. Math. France} \textbf{123} (1995), 271--292.

\bibitem[Fer96]{Ferenczi}
S.~Ferenczi,
\newblock Rank and symbolic complexity,
\newblock {\em Ergodic Theory Dynam. Systems} \textbf{16} (1996), 663--682.

\bibitem[Fer99]{ferenczi_survey}
S.~Ferenczi,
\newblock Complexity of sequences and dynamical systems,
\newblock {\em Discrete Math.} \textbf{206} (1999), 145--154.

\bibitem[FM97]{FerencziMauduit97}
S.~Ferenczi and C.~Mauduit,
\newblock Transcendence of numbers with a low complexity expansion,
\newblock {\em J. Number Theory} \textbf{67} (1997), 146--161.

\bibitem[Fog02]{Pytheas-Fogg}
N.~Pytheas Fogg,
\newblock {\em Substitutions in Dynamics, Arithmetics and Combinatorics},
 {\em Lecture Notes in Mathematics}, Vol.\ 1794,
\newblock Springer-Verlag, 2002.
\newblock Edited by V. Berth{\'e}, S. Ferenczi, C. Mauduit, and A. Siegel.

\bibitem[Fog11]{Cassaigne_S-adic}
N.~Pytheas Fogg,
\newblock Terminologie {$S$}-adique et propri\'et\'es,
\newblock Preprint available at
  \url{http://tinyurl.com/8opdb8s}, 2011.

\bibitem[GJ00]{Gjerde:2000}
R.~Gjerde and {\O}.~Johansen,
\newblock Bratteli-{V}ershik models for {C}antor minimal systems:  applications to {T}oeplitz flows,
\newblock {\em Ergodic Theory Dynam. Systems}, \textbf{20} (2000), 1687--1710.

\bibitem[GJ09]{Glen-Justin}
A.~Glen and J.~Justin,
\newblock Episturmian words: a survey,
\newblock {\em Theor. Inform. Appl.} \textbf{43} (2009), 403--442.

\bibitem[Gri73]{Grillenberger}
C.~Grillenberger,
\newblock Constructions of strictly ergodic systems. {I}. {G}iven entropy,
\newblock {\em Z. Wahrscheinlichkeitstheorie und Verw. Gebiete} \textbf{25} (1972/73), 323--334.

\bibitem[HZ98]{HoltonZamboni98}
C.~Holton and L.Q.~Zamboni,
\newblock Geometric realizations of substitutions,
\newblock {\em Bull. Soc. Math. France} \textbf{126} (1998), 149--179.

\bibitem[JV00]{Justin-Vuillon}
J.~Justin and L.~Vuillon,
\newblock Return words in {S}turmian and episturmian words,
\newblock {\em RAIRO Theor. Inform. Appl.} \textbf{34} (2000), 343--356.

\bibitem[Kos98]{koskas}
M.~Koskas,
\newblock Complexit\'es de suites de {T}oeplitz,
\newblock {\em Discrete Math.}, \textbf{183} (1998), 161--183.

\bibitem[Ler12a]{Leroy_these}
J.~Leroy,
\newblock {\em Contribution to the resolution of the {$S$}-adic conjecture},
\newblock PhD thesis, Universit\'e de Picardie Jules Verne, 2012.

\bibitem[Ler12b]{Leroy}
J.~Leroy,
\newblock Some improvements of the {$S$}-adic conjecture,
\newblock {\em Adv. in Appl. Math.} \textbf{48} (2012), 79--98.

\bibitem[LR]{Leroy-Richomme}
J.~Leroy and G.~Richomme,
\newblock A combinatorial proof of {$S$}-adicity for sequences with sub-affine
  complexity, 
\newblock {\em Integers}, to appear.

\bibitem[LR07]{LR07}
F.~Lev\'e, G.~Richomme,
\newblock Quasiperiodic Sturmian words and morphisms,
\newblock {\em Theoret. Comput. Sci.} \textbf{372} (2007), 15--25.

\bibitem[Lot97]{Lothaire1983}
M.~Lothaire,
\newblock {\em Combinatorics on Words},
\newblock Cambridge Mathematical Library, Cambridge University Press,
  1997.
\newblock (Corrected reprint of the 1983 original.)

\bibitem[Lot02]{Lothaire}
M.~Lothaire,
\newblock {\em Algebraic Combinatorics on Words}, Vol.\ 90 of {\em
  Encyclopedia of Mathematics and its Applications},
\newblock Cambridge University Press, 2002.

\bibitem[MH38]{Morse-Hedlund2}
M.~Morse and G.~A.~Hedlund,
\newblock Symbolic dynamics,
\newblock {\em Amer. J. Math.} \textbf{60} (1938), 815--866.

\bibitem[MH40]{Morse-Hedlund}
M.~Morse and G.~A.~Hedlund,
\newblock Symbolic dynamics {II}. {S}turmian trajectories,
\newblock {\em Amer. J. Math.} \textbf{62} (1940), 1--42.

\bibitem[MM10]{Mauduit-Moreira}
C.~Mauduit and C.~G.~Moreira,
\newblock Complexity of infinite sequences with zero entropy,
\newblock {\em Acta Arith.} \textbf{142} (2010), 331--346.

\bibitem[NP09]{Nicolas-Pritykin}
F.~Nicolas and Y.~Pritykin,
\newblock On uniformly recurrent morphic sequences,
\newblock {\em Internat. J. Found. Comput. Sci.} \textbf{20} (2009), 919--940. 

\bibitem[Pan83]{Pansiot_hierarchical}
J.-J.~Pansiot,
\newblock Hi\'erarchie et fermeture de certaines classes de tag-syst\`emes,
\newblock {\em Acta Inform.} \textbf{20} (1983), 179--196.

\bibitem[Pan84]{Pansiot}
J.-J.~Pansiot,
\newblock Complexit\'e des facteurs des mots infinis engendr\'es par morphismes
  it\'er\'es,
\newblock in {\em Automata, Languages and Programming},
  {\em Lect. Notes in Comput. Sci.}, Vol.\ 172, Springer,
  1984, pp.\ 380--389. 

\bibitem[Pan85]{Pansiot_subword}
J.-J.~Pansiot,
\newblock Subword complexities and iteration,
\newblock {\em Bull. Eur. Assoc. Theor. Comput. Sci. EATCS}, No.\ 26 (1985), 55--62.

\bibitem[Rau82]{Rauzy82}
G.~Rauzy,
\newblock Nombres alg\'ebriques et substitutions,
\newblock {\em Bull. Soc. Math. France} \textbf{110} (1982), 147--178.

\bibitem[Rot94]{Rote}
G.~Rote,
\newblock Sequences with subword complexity {$2n$},
\newblock {\em J. Number Theory} \textbf{46} (1994), 196--213.

\bibitem[RS80]{L_system}
G.~Rozenberg and A.~Salomaa,
\newblock {\em The Mathematical Theory of {L} systems}, Vol.\ 90 of {\em Pure
  and Applied Mathematics},
\newblock Academic Press, 1980.

\bibitem[Sal10]{Salimov}
P.~V.~Salimov,
\newblock On uniform recurrence of a direct product,
\newblock {\em Discrete Math. Theor. Comput. Sci.} \textbf{12} (2010), 1--8.

\bibitem[S{\'e}{\'e}85]{Seebold1985}
P.~S{\'e}{\'e}bold,
\newblock Sequences generated by infinitely iterated morphisms,
\newblock {\em Discrete Appl. Math.} \textbf{11} (1985), 255--264. 

\bibitem[Thu12]{Thue1912}
A.~Thue,
\newblock \"Uber die gegenseitige Lage gleicher Teile gewisser Zeichenreihen,
\newblock {\em Kra. Vidensk. Selsk. Skrifter. I. Math. Nat. Kl.} \textbf{1} (1912), 1--67.

\bibitem[Vui01]{Vuillon_sturmian}
L.~Vuillon,
\newblock A characterization of {S}turmian words by return words,
\newblock {\em European J. Combin.} \textbf{22} (2001), 263--275.

\bibitem[Wil84]{Williams:1984}
S.~Williams
\newblock Toeplitz minimal flows which are not uniquely ergodic,
\newblock {\em Z. Wahrsch. Verw. Gebiete}, \textbf{67} (1984), 95--107. 

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15; Secondary 37B10.

\noindent \emph{Keywords: } 
factor complexity, $S$-adicity, $S$-adic conjecture,
morphism, subword complexity,
linear complexity, uniform recurrence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences
\seqnum{A003849},
\seqnum{A010060}, and
\seqnum{A049320}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  June 23 2012;
revised version received  October 9 2012.
Published in {\it Journal of Integer Sequences}, March 2 2013.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in


\end{document}

                                                                                

.