\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amscd}
\usepackage{graphicx}
\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}
\usepackage{latexsym}
\usepackage{epsf}
\usepackage{breakurl}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\def\vtm{{\bf vtm}}
\newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\underline{#1}}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\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}
\begin{center}
\vskip 1cm{\LARGE\bf
Finite Test Sets for Morphisms That Are \\
Squarefree on Some of Thue's \\
\vskip .1in
Squarefree Ternary Words
}
\vskip 1cm
\large
James D. Currie\\
Department of Mathematics and Statistics\\
University of Winnipeg\\
Winnipeg, Manitoba R3B 2E9 \\
Canada\\
\href{mailto:j.currie@uwinnipeg.ca}{\tt j.currie@uwinnipeg.ca} \\
\end{center}
\vskip .2 in
\begin{abstract}
Let $S$ be one of $\{aba,cbc\}$ and $\{aba, aca\}$, and let $w$ be an infinite squarefree word over $\Sigma=\{a,b,c\}$ with no factor in $S$.
Suppose that $f:\Sigma\rightarrow T^*$ is a non-erasing morphism.
We prove that the word $f(w)$ is squarefree if and only if $f$ is squarefree on factors of $w$ of length 8 or less.
\end{abstract}
\section{Introduction}
The papers of Thue on squarefree words \cite{thue06,thue12} are foundational to the area of combinatorics on words. A word $w$ is {\em squarefree} if we cannot write $w=xyyz$, where $y$ is a non-empty word. The longest squarefree words over the 2-letter alphabet $\{a,b\}$ are $aba$ and $bab$, each of length 3, but Thue showed that arbitrarily long squarefree words exist over the 3-letter alphabet $\{a,b,c\}$. Infinite squarefree words over finite alphabets are routinely encountered in combinatorics on words, and are frequently used as building blocks in constructions. (See, for example, \cite{loth97,loth02}.)
Let $w$ be an infinite squarefree word over $\Sigma=\{a,b,c\}$. Thue showed that $w$ must contain every squarefree word of length 2 over $\Sigma$
. However, he showed that the same is not true for squarefree words of length 3 over $\Sigma$. For each of $S_1=\{aba,cbc\}, S_2=\{aba, aca\}$, and $S_3=\{aba,bab\}$, Thue constructed an infinite squarefree word over $\Sigma$ with no factor in $S_i$. Constructions giving squarefree words equivalent to Thue's word with no factors in $S_1$ were independently discovered by Braunholtz \cite{braunholtz} and Istrail \cite{istrail}; Berstel \cite{berstel78} shows this equivalence. Their word is called $\vtm$ (for `variation of Thue-Morse') by Blanchet-Sadri
et al.~\cite{blanchetsadri}, and has been used as the basis for various constructions \cite{blanchetsadri,currie91,currieetal}. These constructions require showing that $f(\vtm)$ is squarefree for particular morphisms $f$. In this paper, we give a testable characterization of morphisms $f$ such that $f(\vtm)$ is squarefree; we do the same in the case where $\vtm$ is replaced by an infinite squarefree word over $\Sigma$ with no factors in $S_2$. We leave as an open problem whether there is a characterization when we replace $\vtm$ by a word over $\Sigma$ with no factor in $S_3$.
\begin{theorem}
Let $w$ be an infinite squarefree word over $\Sigma$ such that either $w$ has no factor in $S_1$, or $w$ has no factor in $S_2$.
Suppose that $f:\Sigma\rightarrow T^*$ is a non-erasing morphism. The word $f(w)$ is squarefree if and only if $f$ is squarefree on factors of $w$ of length 8 or less.
\end{theorem}
Our theorem says that to establish squarefreeness of $f(w)$,
the morphism $f$ need only be checked for squarefreeness on a finite test set. Crochemore \cite{crochemore} proved a variety of similar theorems; in particular, a morphism $f$ defined on $\Sigma^*$ preserves squarefreeness exactly when $f$ preserves squarefreeness on words of $\Sigma^*$ of length at most 5. Note that while Crochemore's theorem requires testing the squarefreeness of $f(v)$ for every squarefree word $v\in\Sigma^*$ up to a certain length, we only test words $v$ that are factors of $w$. Thus, while $aba$ is squarefree, we do not require $f(aba)$ to be squarefree, for example. Finite test sets for morphisms preserving overlap-freeness have also been well-studied \cite{richomme}.
\section{Preliminaries}
Let $S=S_1$ or $S=S_2$. For the remainder of this paper, let $w$ be an infinite squarefree word over $\Sigma$ with no factor in $S$.
Write $w=a_0a_1a_2a_3\cdots$ with $a_i\in\Sigma.$
For the remainder of this section suppose that $f:\Sigma\rightarrow T^*$ is a non-erasing morphism that is squarefree on factors of $w$ of length 8 or less.
\begin{lemma}\label{at most 3}Suppose $f(\xi)$ is a factor of $f(x)$, where $x\in\Sigma$ and $\xi$ is a factor of $w$. Then $|\xi|\le 3$.
\end{lemma}
\begin{proof} If $x$ is a letter of $\xi$, but $f(\xi)$ is a factor of $f(x)$, we have
\begin{eqnarray*}
|f(x)|&\le&|f(\xi)|\\
&\le&|f(x)|.
\end{eqnarray*}
Since $f$ is non-erasing, this forces $x=\xi$, giving $|\xi|=1$.
If $x$ is not a letter of $\xi$, then $\xi$ is a squarefree word over a two-letter alphabet, so that $|\xi|\le 3.$
\end{proof}
\begin{lemma}\label{no prefix}Suppose that
$f(x)$ is a prefix or a suffix of $f(y)$ where $x,y\in\Sigma$. Then $x=y$.
\end{lemma}
\begin{proof}
We give the proof where $f(x)$ is a prefix of $f(y)$. (The other case is similar.) Suppose
$x\ne y$. Then
$xy$ must be a factor of $w$, and $xy$ is squarefree. However, $f(xy)$ begins with the square $f(x)f(x)$, contradicting the squarefreeness of $f$ on factors of $w$ of length at most 8.\end{proof}
\begin{lemma}\label{suffix} There is no solution $(\alpha,\beta,\gamma,\xi,p,s,t,x,y,z)$ to
\begin{eqnarray*}
&&\alpha\xi xyz\beta\mbox{ is a factor of }w;\\
&&\alpha,\beta,\gamma,x,y,z\in\Sigma, \xi\in\Sigma^*;\\
&&t\mbox{ is a suffix of }f(\gamma);\\
&&s\mbox{ is a suffix of } f(\alpha);\\
&&p\mbox{ is a non-empty prefix of }f(\beta);\\
&&t=sf(\xi xyz)p.
\end{eqnarray*}
\end{lemma}
\begin{proof}
Suppose, for the sake of getting a contradiction,
that $(\alpha,\beta,\gamma,\xi,p,s,t,x,y,z)$ is a solution.
Here $p$ is a prefix of $f(\beta)$, but also a suffix of $t$, that is a suffix of $f(\gamma)$. Thus we see that $f(\gamma\beta)$ contains square $pp$, so that $\gamma\beta$ is not a factor of $w$. This forces $\gamma=\beta$. On the other hand, since $z\beta$ is a factor of $w$, we conclude that $z\ne \gamma$. Again, $f(z)p$ is a prefix of $f(z\beta)$, but also a suffix of $f(\gamma)$, so that $f(\gamma z\beta)$ contains a square. Since $yz\beta$ is a factor of $w$, it follows that $y\ne \gamma$. Similarly, $f(\gamma yz\beta)$ contains a square, but $xyz\beta$ is a factor of $w$, so that that $x\ne \gamma$. Finally, we see that
$f(\gamma xyz\beta)$ contains a square.
Let $\delta$ be the last letter of $\alpha\xi$. We conclude that $\delta\ne \gamma$. However, now $\delta xyz$ is a squarefree word of length 4 over the two-letter alphabet $\Sigma-\{\gamma\}$. This is impossible.
\end{proof}
The symmetrical lemma is proved analogously:
\begin{lemma}\label{prefix} There is no solution $(\alpha,\beta,\gamma,\xi,p,s,t,x,y,z)$ to
\begin{eqnarray*}
&&\alpha\xi xyz\beta\mbox{ is a factor of }w;\\
&&\alpha,\beta,\gamma,x,y,z\in\Sigma, \xi\in\Sigma^*;\\
&&t\mbox{ is a suffix of }f(\gamma);\\
&&s\mbox{ is a non-empty suffix of } f(\alpha);\\
&&p\mbox{ is a non-empty of }f(\beta);\\
&&t=sf(xyz\xi)p.
\end{eqnarray*}
\end{lemma}
Suppose that $f(w)$ contains a non-empty square $xx$, with $|x|$ as short as possible. Write
$f(w)=uxxv$, such that
\begin{align*}
u &=A_0A_1\cdots A_i' \\
ux &=A_0A_1\cdots A_j' \\
uxx &=A_0A_1\cdots A_k',
\end{align*}
where $i\le j\le k$ are non-negative integers, and for each non-negative integer $\ell$, $A_\ell=f(a_\ell)$, and $A_\ell'$ is a prefix of $A_\ell$, but $A_\ell'\ne A_\ell$. This notation is not intended to exclude the possibilities that $i=0$, $i=j$ and/or $j=k$.
\begin{remark}
Since $f$ is squarefree on factors of $w$ of length at most 8, but $f(a_i\cdots a_k)$ contains the square $xx$, we must have $k-i\ge 8$.
\end{remark}
\begin{remark}
We cannot have $i=j$; otherwise suffix $x$ of $ux$ is a factor of $A_j=A_i$, and $A_{i+1}\cdots A_{k-1}$ is a factor of suffix $x$ of $uxx$. Then, $f(a_{i+1}a_{i+2}\cdots a_{k-1})$ is a factor of $f(a_i)$, forcing $(k-1)-(i+1)+1\le 3$ by Lemma~\ref{at most 3}, so that $k-i\le 4$, a contradiction. Reasoning, in the same way, we show that $i|x|$. Then
$|A_j^{\prime\prime}|>|x|-|A_j'|=|A_i^{\prime\prime}A_{i+1}\cdots A_{j-1}|$. It follows that $A_j^{\prime\prime}=A_i^{\prime\prime}A_{i+1}\cdots A_{j-1}A_j^{\prime\prime\prime}$ for some non-empty prefix $A_j^{\prime\prime\prime}$ of $A_j$. Similarly, one shows that $A_j^{\prime}=A_j^{\prime\prime\prime\prime}A_{j+1}\cdots A_{k-1}A_k'$ for some non-empty suffix $A_j^{\prime\prime\prime\prime}$ of $A_j$. Now $|a_{i+1}\cdots a_{j-1}|=(j-1)-(i+1)+1=j-i-1$, and $|a_{j+1}\cdots a_{k-1}|=(k-1)-(j+1)+1=k-j-1$. However, either
$j-i-1\ge 3$, or $k-j-1\ge 3$. If $j-i-1\ge 3$, then
$A_j^{\prime\prime}=A_i^{\prime\prime}A_{i+1}\cdots A_{j-1}A_j^{\prime\prime\prime}$ for some non-empty prefix $A_j^{\prime\prime\prime}$ of $A_j$ contradicts
Lemma~\ref{suffix}, letting $s=A_i^{\prime\prime}$, $\alpha = a_i$,
$\xi= a_{i+1}\cdots a_{j-4}$, $xyz=a_{j-3}a_{j-2}a_{j-1}$, $p=A_j^{\prime\prime\prime}$, $\beta=a_j$.
In the case where $k-j-1\ge 3$, we get the analogous contradiction using
Lemma~\ref{prefix}.
\end{proof}
\begin{lemma}\label{lineup} We have $j-i=k-j$, $A_i^{\prime\prime}=A_j^{\prime\prime}$,
$A_j^{\prime}=A_k^{\prime}$, and $A_{i+\ell}=A_{j+\ell}$, $1\le \ell\le j-i-1$.
\end{lemma}
\begin{proof}
To begin with we show that $A_j^{\prime}=A_k^{\prime}$. Since both words are suffixes of $x$, it suffices to show that
$|A_j^{\prime}|=|A_k^{\prime}|$. Suppose not.
Suppose that $|A_k^{\prime}|<|A_j^{\prime}|$.
By the previous lemma, $|A_j^{\prime}|\le|A_{j+1}\cdots A_{k-2}A_{k-1}A_k'|$. Let $m$ be greatest such that $|A_m\cdots A_{k-1}A_k'|\ge
|A_j^{\prime}|$. Thus $j+1\le m\le k-1$, and
$$|A_{m+1}\cdots A_{k-1}A_k'|<|A_j^{\prime}|\le |A_mA_{m+1}\cdots A_{k-1}A_k'|.$$
If $A_j^{\prime}=A_mA_{m+1}\cdots A_{k-1}A_k'$, then
$A_m$ is a non-empty prefix of $A_j^{\prime}$, forcing $a_m=a_j$ so that $A_m=A_j^{\prime}=A_j$, by Lemma~\ref{no prefix}. This is contrary to our choice of $A_j^{\prime}$.
Similarly, suppose $|A_k^{\prime}|<|A_j^{\prime}|$.
Suppose that $|A_k^{\prime}|<|A_j^{\prime}|$.
Again by the previous lemma, $|A_k^{\prime}|\le|A_{i+1}\cdots A_{j-2}A_{j-1}A_j'|$. Let $m$ be greatest such that $|A_m\cdots A_{j-1}A_j'|\ge
|A_k^{\prime}|$. Thus $i+1\le m\le j-1$, and
$$|A_{m+1}\cdots A_{j-1}A_j'|<|A_k^{\prime}|\le |A_mA_{m+1}\cdots A_{j-1}A_j'|.$$
If $A_k^{\prime}=A_mA_{m+1}\cdots A_{j-1}A_j'$, then
$A_m$ is a non-empty prefix of $A_k^{\prime}$, forcing $a_m=a_k$ so that $A_m=A_k^{\prime}=A_k$, by Lemma~\ref{no prefix}, contrary to our choice of $A_k^{\prime}$.
We thus conclude that $A_j'=A_k'$, as desired.
Next, we show that $j-1=k-j$ and $A_{i+\ell}=A_{j+\ell}$, $1\le \ell\le j-i-1$. Suppose that $j-i\le k-j$. (The other case is similar.)
Suppose now that we have shown that for some $\ell$, $0\le \ell< j-i-1$ that
\begin{equation}\label{IHOP}A_{j-\ell}\cdots A_{j-1}A_j'=A_{k-\ell}\cdots A_{k-1}A_k'.\end{equation}
This is true when $\ell=0$; i.e., $A_j^{\prime}=A_k^{\prime}$.
From (\ref{x=x}), one of $A_{j-\ell-1}A_{j-\ell}\cdots A_{j-1}A_j'$ and $A_{k-\ell-1}A_{k-\ell}\cdots A_{k-1}A_k'$
is a suffix of the other. Together with (\ref{IHOP}), this implies that
one of $A_{j-\ell-1}$ and
$A_{k-\ell-1}$
is a suffix of the other.
By Lemma~\ref{no prefix}, this implies that $a_{j-\ell-1}=a_{k-\ell-1}$, and by combining this with (\ref{IHOP}),
\begin{equation}A_{j-\ell-1}\cdots A_{j-1}A_j'=A_{k-\ell-1}\cdots A_{k-1}A_k'.\end{equation}
By induction we conclude that
$$A_{j-\ell}\cdots A_{j-1}A_j'=A_{k-\ell}\cdots A_{k-1}A_k',0\le\ell\le j-i-1,$$
which implies $A_{j-\ell}=A_{k-\ell}$, $1\le \ell\le j-i-1$.
In particular, we note that
\begin{equation}\label{var x=x}A_{i+1}\cdots A_{j-1}=A_{k-j+i+1}\cdots A_{k-1}.\end{equation}
If we now have $k-j>j-i$, then $k-j+i>j$, and (\ref{x=x}) and (\ref{var x=x}) imply that
$A_i^{\prime\prime}=A_j^{\prime\prime}A_{j+1}\cdots A_{k-j+i}$. Then $A_{k-j+i}$ is a suffix of $A_i^{\prime\prime}$ and Lemma~\ref{no prefix} forces $A_{k-j+i}=A_i$. Then (\ref{x=x}) and (\ref{var x=x})
force $A_i=A_i^{\prime}$, contrary to our choice of $A_i^{\prime}$.
We conclude that $k-j=j-i$. From (\ref{x=x}) and (\ref{var x=x}) we conclude that $A_i^{\prime\prime}=A_j^{\prime\prime}$, as desired.
\end{proof}
\begin{corollary}The word $w$ contains a factor $\alpha z \beta z \gamma$, $\alpha,\beta,\gamma\in\Sigma$, $\alpha,\gamma\ne \beta$, $|z|\ge 3$, such that $\alpha\beta\gamma$ is not a factor of $w$.
\end{corollary}
\begin{proof} By Lemma~\ref{lineup}, $w$ contains a factor
$\alpha z \beta z \gamma$, where $\alpha=a_i$, $\beta=a_j$, $\gamma=a_k$, $z=a_{i+1}\cdots a_{j-1}=a_{j+1}\cdots a_{k-1}$. This gives $|z|=j-i-1=k-j-1\ge 3$.
Since $w$ is squarefree, we cannot have $a_i=a_j$; otherwise $w$ contains the square $(a_0z)^2$; similarly, $a_j\ne a_k$. To see that $\alpha\beta\gamma$ is not a factor of $w$, we note that $f$ is squarefree on factors of $w$ of length at most 8, but $f(\alpha\beta\gamma)=A_iA_jA_k$ contains the square $(A_i^{\prime\prime} A_j')(A_j^{\prime\prime} A_k')$; this is a square since $A_i^{\prime\prime}=A_j^{\prime\prime}$ and $A_j'=A_k'$. Since $|A_iA_jA_k|=3\le 8$, we conclude that $A_iA_jA_k$ is not a factor of $w$.
\end{proof}
\section{Results}
\begin{lemma}\label{aba,cbc} If $S=\{aba,cbc\}$, the only squarefree words of length 3 that are not factors of $w$ are $aba$ and $cbc$. In addition, $w$ contains no factor of the form $azbza$ or $czbzc$.
\end{lemma}
\begin{proof} Thue \cite{thue12} showed that a squarefree word over $\Sigma$ not containing $aba$ or $cbc$ as a factor contains every other length 3 squarefree word as a factor.
Suppose $w$ contains a factor $azbza$. Since $aba$ is not a factor of $w$, $z\ne \epsilon$. Since $az$ and $bz$ are factors of $w$, and hence squarefree, the first letter of $z$ cannot be $a$ or $b$, and must be $c$. Similarly, the last letter of $z$ must be $c$. But $w$ contains $zbz$, and thus $cbc$. This is a contradiction. Therefore $w$ contains no factor $azbza$.
Replacing $a$ by $c$ and vice versa in the preceding argument shows that $w$ contains no factor $czbzc$.
\end{proof}
Combining the last two lemmas gives this corollary:
\begin{corollary} If $S=\{aba,cbc\}$ and $f:\Sigma^*\rightarrow T^*$ is squarefree on factors of $w$ of length at most 8, then $f(w)$ is squarefree.
\end{corollary}
\begin{lemma}\label{aba,aca} If $S=\{aba,aca\}$, the only squarefree words of length 3 that are not factors of $w$ are $aba$ and $aca$. In addition, $w$ contains no factor of the form $azbza$ or $azcza$, $|z|\ge 3$.
\end{lemma}
\begin{proof} Thue \cite{thue12} showed that a squarefree word over $\Sigma$ not containing $aba$ or $aca$ as a factor contains every other length 3 squarefree word as a factor.
Suppose $w$ contains a factor $azbza$, $|z|\ge 3$. Since $aba$ is not a factor of $w$, $z\ne \epsilon$. Since $az$ and $bz$ are factors of $w$, and hence squarefree, the first letter of $z$ cannot be $a$ or $b$, and must be $c$. Similarly, the last letter of $z$ must be $c$. However, since $az$ is a factor of $w$, but $aca$ is not, the second letter of $z$ cannot be $a$ and must be $b$. Write $z=cbz'c$. Then $azbza=acbz'cbcbz'ca$ contains the square $cbcb$, that is impossible. We conclude that $w$ contains no factor $azbza$, $|z|\ge 3$.
Replacing $c$ by $b$ and vice versa in the preceding argument shows that $w$ contains no factor $azcza$, $|z|\ge 3$.
\end{proof}
\begin{corollary} If $S=\{aba,aca\}$ and $f:\Sigma^*\rightarrow T^*$ is squarefree on factors of $w$ of length at most 8, then $f(w)$ is squarefree.
\end{corollary}
\begin{lemma} The squarefree word $azbza$ where $z=cabcbacabcacbacabcbac$ has no factors $aba$ or $bab$. It follows that any analogous theorem for $S_3$, with an analogous proof, would require us to replace 8 by a value of at least $|azbza|=45.$
\end{lemma}
\begin{proof} This is established by a finite check.
\end{proof}
\section{Acknowledgments}
The author's research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC), [funding reference number 2017-03901]. The author thanks the careful referee and editor for their comments.
\begin{thebibliography}{3}
\bibitem{berstel78} J. Berstel, Sur la construction de mots sans carr\'e,
{\it S\'em. Th\'eor. Nombres Bordeaux} (1978--1979), 18.01--18.15.
\bibitem{berstel95} J. Berstel, {\em Axel Thue's Papers on Repetitions in Words: a Translation}, Publications du Laboratoire de Combinatoire et d'Informatique Math\'ematique {\bf 20} Universit\'e du Qu\'ebec \`a Montr\'eal, 1995.
\bibitem{blanchetsadri} F. Blanchet-Sadri, J. Currie, N. Fox, and N. Rampersad, Abelian complexity of fixed point of morphism $0\rightarrow 012, 1 \rightarrow 02, 2 \rightarrow 1$, {\em INTEGERS} {\bf 14} (2014), A11.
\bibitem{braunholtz} C. Braunholtz, An infinite sequence of three symbols with no adjacent repeats, {\em Amer. Math. Monthly} {\bf 70} (1963), 675--676.
\bibitem{crochemore} M. Crochemore,
Sharp characterizations of squarefree morphisms,
{\em Theoret. Comput. Sci.} {\bf 18} (1982), 221--226.
\bibitem{currie91} J. D. Currie, Which graphs allow infinite nonrepetitive walks?, {\em Discrete Math.} { \bf 87} (1991), 249--260.
\bibitem{currieetal} James Currie, Tero Harju,
Pascal Ochem, and Narad Rampersad,
Some further results on squarefree arithmetic progressions in infinite words,
{\em Theoret. Comput. Sci.} {\bf 799} (2019), 140--148.
\bibitem{istrail} S. Istrail, On irreductible languages and nonrational numbers, {\em Bull. Math. Soc. Sci. Math. R. S. Roumanie} {\bf 21} (1977), 301--308.
\bibitem{loth97}M. Lothaire, {\em Combinatorics on Words}, Cambridge University Press, 1997.
\bibitem{loth02}M. Lothaire, {\em Algebraic Combinatorics on Words}, Cambridge University Press, 2002.
\bibitem{richomme}
G. Richomme and F. Wlazinski,
Overlap-free morphisms and finite test-sets,
{\em Discrete Appl. Math.} {\bf 143} (2004), 92--109.
\bibitem{thue06} Axel Thue, \"{U}ber unendliche Zeichenreihen,
{\em Norske Vid. Selsk. Skr. Mat. Nat. Kl.} {\bf 7} (1906), 1--22.
\bibitem{thue12} Axel Thue, \"{U}ber die gegenseitige Lage gleicher Teile gewisser Zeichentreihen, {\em Norske Vid. Selske Skr. Mat. Nat. Kl.} {\bf 1} (1912), 1--67.
\end{thebibliography}
\bigskip
\hrule
\bigskip
\noindent 2010 {\it Mathematics Subject Classification}:
Primary 68R15.
\noindent \emph{Keywords: } Thue-Morse sequence, squarefree word, nonrepetitive word, factor.
\bigskip
\hrule
\bigskip
\noindent (Concerned with sequences
\seqnum{A010060} and
\seqnum{A036577}.)
\bigskip
\hrule
\bigskip
\vspace*{+.1in}
\noindent
Received October 3 2019;
revised versions received November 30 2019; December 7 2019.
Published in {\it Journal of Integer Sequences},
December 9 2019.
\bigskip
\hrule
\bigskip
\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{https://cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in
\end{document}