%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%   LaTeX for a 7 page article. %
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\documentstyle{article}
\setlength{\topmargin}{.25in}
\setlength{\textheight}{7.5in}
\setlength{\oddsidemargin}{.375in}
\setlength{\evensidemargin}{.375in}
\setlength{\textwidth}{5.75in}

%The following line will define a blackboard bold N if
%you don't have one.
\def\Bbb#1{\rm {I\kern -2pt #1}}


\pagestyle{myheadings}
\markright{\sc the electronic journal of combinatorics 2 (1995), \#R21 \hfill}
\thispagestyle{empty}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{rem}[theorem]{Remark}
\newenvironment{remark}{\begin{rem}\rm}{\end{rem}}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{eg}[theorem]{Example}
\newenvironment{example}{\begin{eg}\rm}{\end{eg}}
\newtheorem{conj}[theorem]{Conjecture}
\newenvironment{conjecture}{\begin{conj}\rm}{\end{conj}}
\newtheorem{prob}[theorem]{Problem}
\newenvironment{problem}{\begin{prob}\rm}{\end{prob}}
\newcommand{\pf}{\noindent {\bf Proof: }}

\begin{document}
\title{A note on antichains of words}
\author{James D. Currie\thanks{This work was supported by an NSERC 
operating grant.}\\
Department of Mathematics and Statistics\\University of 
Winnipeg\\Winnipeg, Manitoba\\Canada R3B 2E9\\currie@uwinnipeg.ca}
\date{Submitted: July 9, 1995; Accepted: October 14, 1995}
\maketitle
\begin{abstract}
We can compress the word `banana' as $xyyz$, where 
$x =$ `b', $y = $ `an',$z = $ `a'. We say that `banana' {\it encounters\/}
$yy$. Thus a `coded' version of $yy$ shows up in `banana'. The
relation `$u$ encounters $w$' is transitive, and thus generates
an order on words. We study antichains under this order. 
In particular we show that in this order
there is 
an infinite antichain of binary 
words 
avoiding overlaps.
\end{abstract}
\medskip
{\bf AMS Subject Classification:} 68R15, 06A99\\
{\bf Key Words:} overlaps. antichains, words avoiding patterns\\


\section{Introduction}
The study of words avoiding patterns is an area of combinatorics
on words reaching back at least to the turn 
of the century, when Thue proved \cite{thue} that one can find arbitrarily 
long words over a 3 letter alphabet in which no two adjacent subwords
are identical. If $w$ is such a word, then $w$ cannot be written 
$w = xyyz$ with $y$ a non-empty
word. In modern parlance, we would say that $w$ {\bf avoids} $yy$. A word
which can be written as $xyyz$ is said to {\bf encounter} $yy$.
Thue also showed that there are arbitrarily long words over a 2 letter
alphabet avoiding $yyy$. One can quickly check that no word of length 4 or 
more over a 2 letter alphabet avoids $yy$. We say that $yyy$ is {\bf
avoidable} on 2 letters, or {\bf 2-avoidable}
whereas $yy$ is {\bf unavoidable} on 2 letters. 
On the other hand, $yyy$ is certainly 3-avoidable, because any
word avoiding $yy$ must avoid $yyy$ also.

Bean, Ehrenfeucht and McNulty \cite{bean}, and 
independently Zimin \cite{zimin}, characterized words which are avoidable
on some large enough finite alphabet. If $p$ is a word over an $n$ letter
alphabet, then $p$ is avoidable on some finite alphabet if $Z_n$ avoids
$p$, where words $Z_n$ are defined recursively by
\begin{eqnarray*}
Z_1&=&1\\
Z_{n+1}&=&Z_n(n+1)Z_n, n\in {\Bbb N}.
\end{eqnarray*}
Thus the pattern $abcacb$ is a pattern over a 3 letter alphabet, and is 
avoided by $Z_3 = 1213121$. It follows that $abcacb$ is avoidable on some
large enough finite alphabet. The size of the smallest alphabet on 
which $abcacb$ is avoidable isn't known. No avoidable pattern 
is known which is not 4-avoidable. The following conjecture is 
given by Baker \cite{LITP}:
\begin{conjecture}
Every avoidable pattern is 4-avoidable.
\end{conjecture}

The following problem has been open since 1979 \cite{bean}:
\begin{problem}
Find an algorithm which given a word $p$ determines the smallest
$k$ such that $p$ is $k$-avoidable.
\end{problem}

Cassaigne and Roth \cite{cassaigne,roth} 
studied
avoidable binary and ternary patterns $p$, giving 
when possible the smallest $k$ for which $p$ is $k$-avoidable. 
In such
work, the  most important patterns are the minimal ones; as discussed above,
$yyy$ is 3-avoidable because it contains $yy$. Similarly, if $w$
is 3-avoidable, then so is $w^R$, the reverse of $w$. 
It follows from
the work of Cassaigne and Roth  
that a binary pattern is 2-avoidable exactly when it encounters one of
$xxx$, $xyxyx$, $xyxxy$, $xxyxyy$, $xyxyyx$ and $xxyyx$.
Consideration of minimal $k$-avoidable patterns leads to
problems such as the following,
posed in \cite{baker}:

\begin{problem}
Write $u\ge w$ if $u$ encounters $w$ or the reversal of $w$. This relation
is a quasi-order, and factoring out the resulting equivalence relation gives 
a partial order. Let $\mu(w)$ be the size
of the smallest alphabet on which $w$ is avoidable. For avoidable
$w$, is there an infinite antichain on $\mu(w)$ letters such that each 
member of the antichain avoids $w$?
\end{problem}

Perhaps the posing of this problem is too ambitious. An
affirmative solution would imply that for any 
avoidable word $w$, it takes no more letters to avoid
$w$ and $w^R$ simultaneously than it does to avoid $w$ alone. Strong
evidence to the contrary is provided by the example $w=abcacb$. It
seems likely that $abcacb$ is 2-avoidable; there are words of length 1000
over $\{0,1\}$
avoiding $abcacb$. However, 
$abcacb$ and $bcacba$ are not simultaneously 2-avoidable.\footnote{Thanks 
to Kirby Baker for the use of his software which allowed
the author to make these discoveries concerning $abcacb$.} 

For this reason, it seems that a better question to ask is the following:
\begin{problem}
Write $u\ge w$ if $u$ encounters $w$. 
For avoidable
$w$, is there an infinite antichain on $\mu(w)$ letters such that each 
member of the antichain avoids $w$?
\end{problem}
This question was answered in the affirmative in the case where $w$
is 2-avoidable in \cite{goralcik}
Note that for the sake of studying antichains it is unnecessary to move
from the quasi-order to a partial order.

In a related paper \cite{crochemore} it was shown that 
for any $\epsilon > 0$
there is an infinite antichain of such ternary words
avoiding $x^k$ for $7/4 < k <7/4+\epsilon.$ Note that
$7/4$ is the {\bf threshold} of repetition for words over a 3 letter
alphabet; if $r < 7/4$,
we can find at most finitely many words over a 3 letter alphabet
avoiding $x^r$.

The threshold of repetition for a 2 letter alphabet is 2. A word 
containing no subwords of the form $x^k$ for $k>2$ is called
{\bf overlap-free}. A word is overlap-free exactly when it avoids 
both the
patterns $xxx$ and $xyxyx$.

In this note we prove that
any binary word
which avoids overlaps is an element of an infinite antichain of binary 
words 
avoiding overlaps. 

\section{Preliminaries}

An {\bf alphabet} $\Sigma$ is a set whose elements
 are called {\bf letters}. A {\bf word} $w$ 
 over $\Sigma$ 
is a finite string of letters from $\Sigma.$ 
The {\bf length} of word $w$ is the 
number of letters 
in $w$, denoted by $|w|.$ Thus $|banana|=6$, for example.
The language consisting of 
all words over $\Sigma$ is denoted by $\Sigma^*.$ 
If $x,y \in \Sigma^*,$ the 
{\bf concatenation} of $x$ and $y$, written $xy$, is simply the 
string consisting 
of $x$ followed by $y.$ 
The word with no letters is called the {\bf empty word} and is denoted by 
$\epsilon.$ 
Suppose $w \in \Sigma^*.$ We call word $x$ a {\bf prefix} of $w$ if $w = xy,$ some
$y \in \Sigma^*.$
Similarly word $y$ is a {\bf suffix} of $w$ if we can write 
$w = xy,$ some $x \in \Sigma^*.$
We call $y$ a {\bf subword} of $w$ if we can write $w = xyz,$ some $x,z \in
\Sigma^*.$ In the case that $x$ and $z$ are non-empty, $y$ is an
{\bf internal subword} of $w$.

Let $\Sigma$, $T$ be alphabets. 
A {\bf substitution} $h: \Sigma^{*}\rightarrow  T^{*}$  
is a function generated 
by its values on $\Sigma.$ That is, suppose $w\in  \Sigma^{*}, \, 
w = a_1 a_2\ldots a_m; \, a_i \in \Sigma$ for $i = 1$ to $m.$ Then 
$h(w) = h(a_1)h(a_2)\ldots h(a_m).$
A substitution is {\bf non-erasing} if for every
$a\in \Sigma$, $|h(a)|\ne \epsilon$.

Let $w,v$ be finite words over some alphabet
$\Sigma$. We say that $w$ {\bf encounters} $v$ if $w=xh(v)y$ for some 
non-erasing substitution $h:\Sigma^*\rightarrow\Sigma^*.$ Otherwise we say 
that $w$ {\bf avoids} $v.$ 
If $x$ is a word we denote by $x^n$ the word consisting of $x$ repeated
$n$ times in a row. Thus $x^2=xx, x^3=xxx$ and so on. We call a word
$w$ a {\bf $k$-power} if $w = x^k,$ some $x \ne \epsilon.$ A 2-power is 
also called a {\bf square}. 
An {\bf overlap} is a word of form $xxx$ or $xyxyx$ for some words $x$
and $y$.
A word $w$ is {\bf $k$-power free} if 
we cannot write $w = xyz$, where 
$y$ is a $k$-power.
Thus $w$ is $k$-power free if $w$ avoids $x^k$.
Similarly one speaks of {\bf square-free} or {\bf overlap-free} words.

An {\bf $\omega$-word} over alphabet $\Sigma$ is
an infinite sequence of letters of $\Sigma.$ If 
$w = \{w_i\}_{i \in \mbox{{\scriptsize {\Bbb N}}}}$ 
is an $\omega$-word over $\Sigma,$ then 
each finite initial segment $w_1, w_2,\ldots,w_n$ of $w$ will
correspond to some  word $w_1w_2\ldots w_n$ of $\Sigma^*.$ 
In this case we say that $w_1w_2\ldots w_n$ is a {\bf prefix
of $\omega$-word $w$.}
If $u$ is an $\omega$-word over $\Sigma$ we
say that $u$ encounters $w$ if some finite prefix of $u$ encounters $w.$ 
Otherwise, we say that $u$ avoids $w.$

We say that $w$ is {\bf $k$-avoidable} if the set of words over 
$\Sigma$ 
avoiding $w$ is infinite, for some, hence for any, 
alphabet $\Sigma$ of size
$k$. Equivalently, $w$ is $k$-avoidable if there is an $\omega$-word
over an alphabet of size $k$ which avoids $w$. 
If $w$ is $k$-avoidable for some $k\in 
{\Bbb N}$ we say that $w$ is {\bf avoidable}. Otherwise, $w$ is
{\bf unavoidable}. Let $S$ be a set of words.
We say that $v$ avoids
$S$ if $v$ avoids each $w\in S.$

Fix an alphabet $\Sigma$. The relation `$w$ encounters $v$' is a
quasi-order on $\Sigma^*$ which
we will abbreviate by $w\ge v.$ 
We will be interested in the quasi-ordered set $\langle\Sigma^*,\ge\rangle.$
\begin{lemma} 
\label{infinite antichain}
Suppose that ${\cal A}\subseteq\Sigma^*$ is an infinite antichain. 
Then there
is an $\omega$-word over $\Sigma$ avoiding ${\cal A}.$
\end{lemma}
\pf Let ${\cal A}=\{w_i\}_{i=1}^\infty.$ 
If $w$ is a non-empty word, denote by $w'$ the word obtained from $w$
by deleting the last letter. 

We claim that for
each $i\in {\Bbb N},w_i'$ avoids ${\cal A}:$ 
If $v\le w_i'$ then $v\le w_i$ by transitivity. Thus if 
$j\ne i,$ then $w_i'$ avoids $w_j,$ because $w_j$ and $w_i$ are 
incomparable.
On the other hand, since $w_i'$ is shorter than 
$w_i,$ certainly $w_i'$ avoids $w_i.$ 

Since ${\cal A}$ is an infinite set of words over a finite alphabet, 
${\cal A}$ contains arbitrarily long words. Thus the set
${\cal A}'=\{w_i'\}_{i=1}^\infty$ contains arbitrarily long words of 
$\Sigma^*$ avoiding ${\cal A}.$ It follows by K\"{o}nig's Infinity
Lemma that there is an $\omega$-word over $\Sigma$ avoiding
${\cal A}.\Box$
\begin{lemma}
Let $S$ be a finite set of avoidable words. 
Then 
there
is an $\omega$-word over a finite alphabet avoiding $S.$
\end{lemma}
\pf This is proved in \cite{bean,zimin}. Let $S = \{s_i:1\le i\le m\}.$
For each $i$ pick $n_i\in {\Bbb N}$ and an $\omega$-word 
$w_i=\{w_{ij}\}_{j=1}^\infty$ over
an alphabet $\Sigma_i$ of size $n_i$ avoiding $s_i.$ 
Then the word
$w = \{(w_{1j},w_{2j},\ldots,w_{mj})\}_{j=1}^\infty$ over
the alphabet $\prod_{i=1}^m \Sigma_i$
avoids $s.\Box$

To avoid $S$ it suffices to avoid a maximal antichain of minimal
elements of $S.$ Thus we could get by with a version of this lemma in
which $S$ was restricted to be an antichain.

\begin{corollary}
Suppose that ${\cal A}\subseteq\Sigma^*$ is a finite antichain. 
Then there
is an $\omega$-word over some finite alphabet avoiding ${\cal A}.$
\end{corollary}
\begin{remark}
It is striking that infinite antichains over finite sets are easier to
avoid than finite antichains! That is, to avoid a finite antichain over
$S$ it may be necessary to move to a larger alphabet, whereas this
is not the case with infinite antichains. To give a concrete example,
let $S$ be the set of all words of length 7 over $\Sigma = \{a, b\}.$
Each word of $S$ is 2-avoidable, but any binary word of length 7
or more encounters an element of $S$.
\end{remark}
An image of $xxx$ or $xyxyx$ under a non-erasing substitution is called an
{\bf overlap}. Note that a prefix of an overlap will be a square.

\begin{theorem}
There is 
an infinite antichain of binary 
words 
avoiding overlaps. 
\end{theorem}
\pf
Following Thue \cite{thue}, 
Define the map $h:\{a,b\}^*\rightarrow
\{a,b\}^*$ by $h(a) = ab, h(b) = ba.$ 
Let $l$ = aabaab. Thus $l^R=baabaa.$ We see that the prefixes of
$l$ which are suffixes of $l^R$ are exactly $a$, $aa$, $aabaa.$
\begin{lemma}
\label{no l in h}
Word $l$ is avoided by 
$h^\omega(a).$
\end{lemma}
\pf This was proved by Cassaigne 
\cite[Section 2.6, Th\'{e}or\`{e}me 2.2]{cassaigne}.
$\Box$
\begin{corollary}
The word $l^R$, the reverse of $l$, is avoided by 
$h^\omega(a).$
\end{corollary}

Let $n\in{\Bbb N}$. Then we can write 
$h^{2n+2}(a)=abbabaabu_nbaababba$ for some word $u_n.$ 
Let
$m_n = aabaabu_nbaabaa.$ 
\begin{remark}
\label{internal}
Word $l$ is a prefix and suffix of each 
$m_n$, but every internal subword of $m_n$ is a subword of
$h^\omega(a).$ It follows that $l$ doesn't appear in $m_n$ internally.
We note that for each $n$, $m_n$ is a palindrome.
\end{remark}
\begin{lemma} Let $n\in{\Bbb N}$. Then the word
$m_n$ is overlap-free.
\end{lemma}
\pf Every internal
subword of $m_n$ is a subword of $h^\omega(a)$, and is overlap-free.
It remains to show that no prefix or suffix of $m_n$ is an overlap.
As $m_n$ is a palindrome, we need only show that no prefix of $m_n$
is an overlap. 

First note that no prefix of $m_n$ is a square of length $12$ or
greater; otherwise the prefix of $m_n$ of length $6$ reappears
internally, i.e. $m_n$ contains an $l$ internally, which is
impossible. It follows that the shortest overlap which is a prefix of
$m_n$ has length at most $11,$ and is a prefix of $m_1.$ Inspection
shows that no prefix of $m_1$ of length $11$ or less is an overlap.$\Box$

\begin{theorem}The set $\{m_n\}_{n\in{\Bbb N}}$ is an antichain.
\end{theorem}
\pf Let $i,j\in{\Bbb N}, i<j.$ Clearly $m_i$ doesn't encounter $m_j$
since $m_j$ is longer than $m_i.$ Suppose, for the sake of a contradiction,
that $m_j$ encounters $m_i.$ Say that $m_j = \alpha f(m_i)\beta$ 
where $f$ is a
non-erasing substitution. 

If $\alpha\ne \epsilon$ then an internal subword of $m_j$ 
encounters 
the prefix $l$ of $m_i.$ Thus a subword of $h^\omega(a)$
encounters $l.$ This is impossible by Lemma~\ref{no l in h}.
Thus $\alpha = \epsilon.$ Symmetrically, $\beta = \epsilon.$

Since $a$ is a prefix of $m_i$, $f(a)$ is a prefix of $m_j.$ Thus
$l$ and $f(a)$ are both prefixes of $m_j$, and one must be a prefix of
the other.
Since $a$ is an internal subword of $m_i$, $f(a)$ is an internal
subword of $m_j.$ Thus $l$ is not a prefix of $f(a).$ We
conclude that $f(a)$ is a proper prefix of $l.$ Symmetrically, $f(a)$ must
be a proper suffix of $l^R,$ the reverse of $l.$ Thus $f(a) = a$, $aa$ or
$aabaa.$ However, $aa$ is a subword of $m_i$, so that $f(aa)$ is
a subword of the overlap-free word $m_j.$ We conclude that $f(a) = a.$

We have so far determined $f(a).$ Now consider $f(b).$ Since $f(m_i) =m_j$
is longer than $m_i,$ the length of $f(b)$ is greater than $1.$
Since $aab$ and $baa$
are subwords of $m_i$, both $aaf(b)$ and $f(b)aa$ are subwords of 
$m_j.$ It follows that $f(b)$ has $b$ as a prefix and
a suffix, since otherwise $aaa$ appears in $m_j$, a contradiction since
$m_j$ is overlap-free. 

Since $aab$ is a prefix of $m_i,$ 
$f(aab) = aaf(b)$ is a prefix of $m_j.$ However, another prefix of $m_j$
is $aabaab.$ Thus one of $f(b)$ and $baab$ is a prefix of the other.
Since $f(b)$ begins and ends with a $b$, we conclude that $baab$ is
a prefix of $f(b).$ As $aab$ appears internally in $m_i$,
we conclude that $f(aab)$ occurs internally in $m_j.$ A prefix
of $f(aab)$ is $aabaab = l.$ It follows that $l$ appears internally in
$m_j$, and hence that $l$ is a subword of $h^\omega(a).$ This contradicts
Lemma~\ref{no l in h}.

The supposition that $m_j$ encounters $m_i$ leads to a contradiction. We
conclude that $m_i$ and $m_j$ are incomparable, and that in fact
$\{m_n\}_{n\in{\Bbb N}}$ is an antichain.
$\Box.$
\begin{thebibliography}{99}
\bibitem{arshon} S. Ar\v{s}on, D\'{e}monstration de l'existence des suites asym\'{e}triques infinies, 
Mat. Sb., (N.S.) {\bf 2}, 769--779; Zbl. {\bf 18}, 115.
\bibitem{LITP} Kirby A. Baker, Some problems on avoidability. Expos\'{e}
au LITP, 1992.
\bibitem{baker}   Kirby A. Baker, George. F. McNulty \& Walter Taylor, Growth problems 
for avoidable words, Theoret. Comput. Sci. {\bf 69} (1989), no. 3, 319--345; MR 
{\bf 91f}:68109.
\bibitem{bean}  Dwight R. Bean, Andrzej Ehrenfeucht \& George McNulty, Avoidable Patterns 
in Strings of Symbols, Pacific J. Math. {\bf 85} (1979), 261--294; MR {\bf 81i}:20075.
\bibitem{brink}  J. Brinkhuis, Non-repetitive sequences on three symbols, Quart. J. 
Math. Oxford Ser.(2) {\bf 34} (1983), 145--149; MR {\bf 84e}:05008.
\bibitem{brown}  T. C. Brown, Is there a sequence on four symbols in which no two adjacent 
segments are permutations of each other?, Amer. Math. Monthly {\bf 78} (1971), 
886--888.
\bibitem{burris}Stanley Burris \& Evelyn Nelson, Embedding the dual of    in the lattice 
of equational classes of semigroups, Algebra Universalis, {\bf 1} (1971/72), 
248--253; MR {\bf 45} \#5257.
\bibitem{cassaigne} Julien Cassaigne, Motifs \'{e}vitables et r\'{e}gularit\'{e}
dans les mots, Th\`{e}se de Doctorat, Universit\'{e} Paris VI, Juillet 1994.
\bibitem{crochemore}Max Crochemore \& Pavel Goralcik, Mutually avoiding 
ternary words of small exponent, Internat. J. Algebra Comput. {\bf 1} (1991)
407--410.
\bibitem{thesis}  James D. Currie, Non-repetitive walks in graphs and digraphs, PhD 
thesis, University of Calgary (1987).
\bibitem{dm}  James D. Currie, Which graphs allow infinite non-repetitive walks? 
Discrete Math. {\bf 87} (1991), 249--260; MR {\bf 92a}:05124.
\bibitem{open} James. D. Currie, Open problems in pattern avoidance, Amer. Math. Monthly {\bf 100} (1993), 790--793.
\bibitem{ages} James. D. Currie, Non-repetitive words: ages and essences, Combinatorica,
to appear.
\bibitem{dekking} F.M.Dekking,Strongly non-repetitive sequences and progression-free 
sets, J. Combin Theory Ser. A, {\bf 27} (1979), 181--185; MR {\bf 81b}:05027.
\bibitem{dejean} Fran\c{c}oise Dejean, Sur un th\'{e}or\`{e}me de Thue, J. Combin. Theory Ser. A {\bf 13} (1972), 90--99.
\bibitem{ent}  Roger C. Entringer, Douglas E. Jackson \& J.A. Schatz, On non-repetitive 
sequences, J. Combin. Theory Ser. A {\bf 16} (1974), 159--164; MR {\bf 48} \#10860.
\bibitem{fife} Earl D. Fife, Binary sequences which contain no BBb, Trans. Amer. 
Math. Soc. {\bf 261} (1980), 115--136;  MR {\bf 82a}:05034
\bibitem{goralcik}Pavel Goralcik \& Tomas Vanicek, Binary
Patterns in Binary Words, Internat. J. Algebra Comput. {\bf 1} (1991)
387--391.
\bibitem{dj}  Andres. del Junco, A transformation with simple spectrum which 
is not rank one,  Canad. J. Math.  {\bf 29} (1977), 655--663; MR {\bf 57} \#6367.
\bibitem{just}  Jacques Justin, Characterization of the repetitive commutative semigroups, 
J. Algebra {\bf 21} (1972), 87--90; MR {\bf 46}\#277.
\bibitem{kar} Juhani Karhum\"{a}ki, On cube-free $\omega$-words generated by binary morphisms, 
Discrete Appl. Math. {\bf 5} (1983), 279--297; MR {\bf 84j}:03081.
\bibitem{Ker} Veikko Ker\"{a}nen, Abelian squares are avoidable on 4 letters, Automata, 
Languages and Programming: Lecture notes in Computer Sciences {\bf 623} (1992) 
Springer-Verlag 4152.
\bibitem{Mig} Filippo Mignosi, Infinite words with linear subword complexity, Theoret. 
Comput. Sci. {\bf 65} (1989), 221--242; MR {\bf 91b}:68093.
\bibitem{morse}  Marston Morse \& Gustav A. Hedlund, Symbolic dynamics I, II, Amer. 
J. Math. {\bf 60} (1938), 815--866; {\bf 62} (1940) 142; MR {\bf 1}, 123d.
\bibitem{nov}  P. S. Novikov \& S. I. Adjan, Infinite periodic groups I, II, III, 
Izv. Akad. Nauk. SSSR Ser. Mat. {\bf 32} (1968), 212--244;251--524;709--731;MR {\bf 39} \#1532a--c.
\bibitem{ple}  P. A. B. Pleasants, Non-repetitive sequences, Proc. Cambridge Philos. 
Soc. {\bf 68} (1970), 267--274; MR {\bf 42} \#85.
\bibitem{roth} Peter Roth, Every binary pattern of length six
is avoidable on the two-letter alphabet, Interner Bericht 6/89, Fachbereich
Informatik, Universit\"{a}t Frankfurt.
\bibitem{s1}  Robert. O. Shelton \& Raj P. Soni, Aperiodic words on three symbols 
I, II, III, J. reine agnew. Math. {\bf 321;327;330} (1981), 195--209;1--11;44--52; 
{MR {\bf 82m}:05004a--c.}
\bibitem{thue}  Axel Thue, \"{U}ber unendliche Zeichenreihen, Norske Vid. Selsk. Skr. 
I. Mat. Nat. Kl. Christiana (1912), 1--67.
\bibitem{zimin} A. Zimin, Blocking sets of terms, Mat. Sb. (N.S.) {\bf 119} {\bf (161)} (1982); 
Math. USSR Sbornik {\bf 47} (1984), 353--364.
\end{thebibliography}
\end{document}




.
