\documentclass[12pt]{article}
\usepackage{e-jc}
\specs{P2.7}{21(2)}{2014}

%% The following is enclosed to allow easy detection of differences in
%% ascii coding.
%% Upper-case    A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
%% Lower-case    a b c d e f g h i j k l m n o p q r s t u v w x y z
%% Digits        0 1 2 3 4 5 6 7 8 9
%% Exclamation   !           Double quote "          Hash (number) #
%% Dollar        $           Percent      %          Ampersand     &
%% Acute accent  '           Left paren   (          Right paren   )
%% Asterisk      *           Plus         +          Comma         ,
%% Minus         -           Point        .          Solidus       /
%% Colon         :           Semicolon    ;          Less than     <
%% Equals        =           Greater than >          Question mark ?
%% At            @           Left bracket [          Backslash     \
%% Right bracket ]           Circumflex   ^          Underscore    _
%% Grave accent  `           Left brace   {          Vertical bar  |
%% Right brace   }           Tilde        ~

\usepackage{amsthm,amsmath,amssymb}
%\usepackage{url}
\usepackage{srcltx} 
\usepackage{enumerate}
\usepackage[utf8]{inputenc}
\usepackage{mathrsfs}
\usepackage{enumerate}
\usepackage{xcolor}
%\usepackage{xspace}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}

\usepackage[ruled,vlined]{algorithm2e}
\usepackage{xspace}
\usepackage{framed}

\def\paren#1{\left( #1 \right)}
\def\acc#1{\left\{ #1 \right\}}
\def\floor#1{\left\lfloor #1 \right\rfloor}
\def\ceil#1{\left\lceil #1 \right\rceil}

\newcommand{\set}[1]{\{#1\}}
\newcommand{\LP}{\mathcal{LP}}
\newcommand{\ap}{\textsc{AvoidP}\xspace}

\newenvironment{proofof}[1]{\par \noindent \textit{Proof of #1.}
}{\hfill$\Box$\medskip} 

% declare theorem-like environments
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{observation}[theorem]{Observation}
\newtheorem{claim}[theorem]{Claim}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{open}[theorem]{Open Problem}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{question}[theorem]{Question}

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

\makeatletter
\newenvironment{vRule}{
\def\FrameCommand{{\color{black}\vrule width 1pt}\hspace{10pt}}\framed {\advance\hsize-\width}}
{\endframed\vspace{-10pt}\hrule width 10pt height 1pt}
\makeatother 

%% \makeatletter
%% \newenvironment{vRule}{
%% \def\FrameCommand{{\color{black}\vrule width 1pt}\hspace{10pt}}\MakeFramed {\advance\hsize-\width \FrameRestore}}
%% {\endMakeFramed\vspace{-10pt}\hrule width 10pt height 1pt}
%% \makeatother 

\newenvironment{exampleruled}
{\begin{example}\ \begin{vRule}}
{\end{vRule}\end{example}}

\title{\bf Application of entropy compression\\ in pattern avoidance}

\author{Pascal Ochem \qquad Alexandre Pinlou\thanks{Second
    affiliation: Département MIAp, Université Paul-Valéry, Montpellier
    3, Route de Mende, 34199 Montpellier, France.}\\
\small LIRMM, Université Montpellier 2, CNRS\\[-0.8ex]
\small Montpellier, France \\[-0.8ex] 
\small\tt \{pascal.ochem,alexandre.pinlou\}@lirmm.fr\\
}

\date{\dateline{Jan 7, 2013}{Mar 25, 2014}{Apr 16, 2014}\\
\small Mathematics Subject Classifications: 68R15}

\setcounter{secnumdepth}{4} 

\begin{document}

\maketitle

\begin{abstract}
  In combinatorics on words, a word $w$ over an alphabet $\Sigma$ is
  said to avoid a pattern $p$ over an alphabet $\Delta$ if there is no
  factor $f$ of $w$ such that $f= h(p)$ where $h:
  \Delta^*\to\Sigma^*$ is a non-erasing morphism. A pattern $p$ is
  said to be $k$-avoidable if there exists an infinite word over a
  $k$-letter alphabet that avoids $p$. We give a positive answer to
  Problem 3.3.2 in Lothaire's book ``Algebraic combinatorics on
  words'', that is, every pattern with $k$ variables of length at least
  $2^k$ (resp. $3\times2^{k-1}$) is 3-avoidable (resp. 2-avoidable).
  This conjecture was first stated by Cassaigne in his thesis in 1994.
  This improves previous bounds due to Bell and Goh, and Rampersad.

  \bigskip\noindent \textbf{Keywords:} Word; Pattern avoidance.
\end{abstract}

%%%%%%%%%%%%%%%%%%%%%
\section{Introduction}\label{sec:intro}
%%%%%%%%%%%%%%%%%%%%%

A pattern $p$ is a non-empty word over an alphabet
$\Delta=\{A,B,C,\dots\}$ of capital letters called \emph{variables}.
An \emph{occurrence} of $p$ in a word $w$ is a non-erasing morphism $h: \Delta^*\to\Sigma^*$
such that $h(p)$ is a factor of $w$.
The avoidability index $\lambda(p)$ of a pattern $p$ is the size of the
smallest alphabet $\Sigma$ such that there exists an infinite word $w$
over $\Sigma$ containing no occurrence of $p$.
Bean, Ehrenfeucht, and McNulty~\cite{BEM79} and Zimin~\cite{Zimin}
characterized unavoidable patterns, i.e., such that $\lambda(p)=\infty$.
We say that a pattern $p$ is $t$-avoidable if $\lambda(p)\le t$.
For more informations on pattern avoidability, we refer to Chapter 3 of Lothaire's book~\cite{Lothaire:2002}.

In this paper, we consider upper bounds on the avoidability index of
long enough patterns with $k$ variables. Bell and Goh~\cite{BellGoh:2007}
and Rampersad~\cite{Rampersad:2011} used a method based on power series
and obtained the following bounds. Let
$v(p)$ be the number of distinct variables of the pattern~$p$. 
\begin{theorem}[\cite{BellGoh:2007,Rampersad:2011}]
\label{BGR}
Let $p$ be a pattern.
\begin{enumerate}[$\quad$(a)]
\item If $p$ has length at least $2^{v(p)}$ then
 $\lambda(p)\le4$.~\cite{BellGoh:2007}
\item If $p$ has length at least $3^{v(p)}$ then
 $\lambda(p)\le3$.~\cite{Rampersad:2011}
\item If $p$ has length at least $4^{v(p)}$ then
 $\lambda(p)=2$.~\cite{Rampersad:2011}
\end{enumerate}
\end{theorem}

Our main result improves these bounds:
\begin{theorem}
\label{2tok}
Let $p$ be a pattern.
\begin{enumerate}[$\quad$(a)]
\item If $p$ has length at least $2^{v(p)}$ then $\lambda(p)\le3$.\label{2tok-a}
\item If $p$ has length at least $3\times2^{{v(p)}-1}$ then $\lambda(p)=2$.\label{2tok-b}
\end{enumerate}
\end{theorem}

\newcommand{\refa}{\ref{2tok}.(\ref{2tok-a})\xspace}
\newcommand{\refb}{\ref{2tok}.(\ref{2tok-b})\xspace}

Theorem~\ref{2tok} gives a positive answer to Problem 3.3.2 of
Lothaire's book~\cite{Lothaire:2002}. As noticed by
Cassaigne~\cite{Cassaigne:1994,Lothaire:2002}, both bounds of
Theorem~\ref{2tok} are tight. The bound $2^{v(p)}$ in Theorem~\refa is
tight in the sense that the patterns $p$ in the family
$\{A,ABA,ABACABA,$ $ABACABADABACABA,\dots\}$ have length $2^{v(p)}-1$ and are
unavoidable. Similarly, the bound $3\times2^{{v(p)}-1}$ in Theorem~\refb is
tight in the sense that the patterns in the family
$\{AA,AABAA,AABAACAABAA,AABAACAABAADAABAACAABAA,\dots\}$ have length
$3\times2^{{v(p)}-1}-1$ and are not 2-avoidable. Hence, this shows that the
upper bound $3$ of Theorem~\refa is best possible.

\medskip

The avoidability index of every pattern with at most 3 variables is
known, thanks to various results in the literature. In particular,
Theorem~\ref{2tok} is proved for every pattern $p$ with ${v(p)}\le 3$:
\begin{itemize}
\item For ${v(p)}=1$, the famous results of Thue~\cite{Thue06,Thue12} give
$\lambda(AA)=3$ and $\lambda(AAA)=2$.
\item For ${v(p)}=2$, every binary pattern of length at least 4 contains a
square, and is thus 3-avoidable. Moreover, Roth~\cite{Roth:1992}
proved that every binary pattern of length at least 6 is 2-avoidable.
\item For ${v(p)}=3$, Cassaigne~\cite{Cassaigne:1994} began and the first
author~\cite{Ochem:2004} finished the determination of the
avoidability index of every pattern with at most 3 variables. Every
ternary pattern of length at least 8 is 3-avoidable and every binary
pattern of length at least 12 is 2-avoidable.
\end{itemize}
So, there remains to prove Theorem~\ref{2tok} for every pattern $p$
with $v(p) \ge 4$.

\medskip 
Section~\ref{sec:preliminary} is devoted to some preliminary results.
We prove Theorem~\refa in Section~\ref{3-a} as a corollary of
a result of Bell and Goh~\cite{BellGoh:2007}. In Section~\ref{2-a}, we
prove Theorem~\refb using the so-called \emph{entropy compression method}. 

\medskip

Very recently, Blanchet-Sadri and Woodhouse~\cite{Blanchet:2013}
independently proved Theorem~\ref{2tok} using completely different
methods. 

%%%%%%%%%%%%%%%%%%%%%
\section{Preliminary results}\label{sec:preliminary}
%%%%%%%%%%%%%%%%%%%%%

Let $p$ be a pattern over $\Delta=\set{A,B,C,\ldots}$.
An \emph{occurrence} of $p$ in a word $w$ over the alphabet $\Sigma$ is a non-erasing morphism
$h: \Delta^*\to\Sigma^*$ such that $h(p)$ is a factor of $w$.
Note that two distinct occurrences of $p$ may form the same factor.
For example, if $p=ABA$, then the occurrence $h=(A\to00; B\to1)$ of
$p$ forms the factor $h(p) = h(ABA) = h(A)h(B)h(A) = 00100$; on the
other hand, $h'=(A\to0; B\to010)$ is a distinct occurrence of $p$ which
forms the same factor $h'(p) = h'(ABA) = h'(A)h'(B)h'(A) = 00100$. 

A pattern $p$ is \emph{doubled} if every variable of $p$ appears at
least twice in $p$. A pattern $p$ is \emph{balanced} if it is doubled
and every variable of $p$ appears both in the prefix and the suffix of
length $\floor{\frac{|p|}{2}}$ of $p$. Note that if the pattern has
odd length, then the variable $X$ that appears in the middle of $p$
(i.e. in position $\floor{\frac{|p|}{2}} + 1$) must appear also in the
prefix and in the suffix in order to make $p$ balanced.

\begin{claim}\label{cl:balanced}
  For every integer $f\ge 2$, every pattern $p$ with length at least
  $f\times 2^{v(p)-1}$ contains a balanced pattern $p'$ with length at
  least $f\times 2^{v(p')-1}$ as a factor.
\end{claim}

\begin{proof}
  We prove this claim by induction on $v(p)$. If $v(p)=1$, then $p$
  has size at least $f\ge 2$ and is clearly balanced. Suppose this is
  true for some $v(p)=n$, i.e. $p$ with $n$ variables and length at
  least $f\times 2^{n-1}$ contains a balanced pattern $p'$ as a factor
  with length at least $f\times 2^{v(p')-1}$. Let $v(p)=n+1$ and let
  $p_1$ (resp. $p_2$) be the prefix (resp. the suffix) of $p$ of size
  $\floor{\frac{|p|}{2}}$. If $p$ is not balanced, then there exists a
  variable $X$ in $p$ that does not occur in $p_i$ for some
  $i\in\{1,2\}$. Thus, we have $v(p_i) \le v(p)-1=n$ and $|p_i|\ge
  f\times 2^{n-1}$. Therefore, by induction hypothesis, $p$ contains a
  balanced pattern $p'$ with length at least
  $f\times 2^{v(p')-1}$ as a factor.
\end{proof}

In the following, we will only use the fact that the pattern $p'$ in
Claim~\ref{cl:balanced} is doubled instead of balanced.

%%%%%%%%%%%%%%%%%%%%%
\section{3-avoidable long patterns}\label{3-a}
%%%%%%%%%%%%%%%%%%%%%
We prove Theorem~\refa as a corollary of
the following result of Bell and Goh~\cite{BellGoh:2007}:
\begin{lemma}[\cite{BellGoh:2007}]
\label{k6doubled}
Every doubled pattern with at least 6 variables is 3-avoidable.
\end{lemma}

\begin{proofof}{Theorem~\refa}
  We want to prove that every pattern $p$ with length at least
  $2^{v(p)}$ is 3-avoidable, or equivalently, that every pattern $p$
  with ${v(p)}\le k$ and length at least $2^k$ is 3-avoidable. By
  Claim~\ref{cl:balanced}, every such pattern contains a doubled
  pattern $p'$ as a factor with length
  at least $2^{v(p')}$. So there remains to show that every doubled
  pattern $p$ with ${v(p)}\le k$ and length at least $2^k$ is
  $3$-avoidable. As discussed in the introduction, the case of
  patterns with at most $3$ variables has been settled. Now, it is
  sufficient to prove that doubled patterns of length at least
  $2^4=16$ are 3-avoidable.
  
  Suppose that $p_1$ is a doubled pattern containing a variable $X$
  that appears at least 4 times. Replace $2$ occurrences of $X$ with a
  new variable to obtain a pattern $p_2$. Example: We replace the
  first and third occurrence of $B$ in $p_1=ABBCDBCABDDCB$ by a new
  variable $E$ to obtain $p_2=AEBCDECABDDCB$. Then $p_2$ is a doubled
  pattern such that $|p_1|=|p_2|$ and $\lambda(p_1)\le\lambda(p_2)$,
  since every occurrence of $p_1$ is also an occurrence of $p_2$.
  
  Given a doubled pattern $p$ of length at least $16$, we make such
  replacements as long as we can. We thus obtain a doubled pattern
  $p'$ of length at least $16$ such that $\lambda(p)\le\lambda(p')$.
  Moreover, every variable in $p'$ appears either $2$ or $3$ times and
  therefore $p'$ contains at least $\ceil{16/3}=6$ variables. So $p'$
  is $3$-avoidable by Lemma~\ref{k6doubled}. Thus $p$ is
  $3$-avoidable, which finishes the proof.
\end{proofof}

%%%%%%%%%%%%%%%%%%%%%
\section{2-avoidable long patterns}\label{2-a}
%%%%%%%%%%%%%%%%%%%%%

We want to prove that every pattern $p$ with length at least $3\times
2^{v(p)-1}$ is 2-avoidable, or equivalently, that every pattern $p$
with $v(p)\le k$ variables and length at least $3\times 2^{k-1}$ is
2-avoidable. By Claim~\ref{cl:balanced}, every such pattern contains a
doubled pattern $p'$ as a factor with length at least $3\times
2^{v(p')-1}$. So there remains to show that every doubled pattern $p$ with
$v(p) \le k$ and length at least $3\times 2^{k-1}$ is
$2$-avoidable.

As discussed in the introduction, the case of patterns with at most
$3$ variables has been settled. Now, it is sufficient to prove
Theorem~\refb for doubled patterns with at least $4$ variables.

Let $\Sigma=\set{0,1}$ be the alphabet. For the remaining of this
section, let $k\ge 4$ and $q(k)=3\times 2^{k-1}$.

Suppose by contradiction that there exists a doubled pattern $p$ on
$k$ variables and length at least $q(k)$ that is not $2$-avoidable.
Then there exists an integer $n$ such that every word $w\in\Sigma^n$
contains $p$. We put an arbitrary order on the $k$ variables of $p$
and call $A_j$ the $j$-th variable of $p$.

%%%%%%%%%%%%%%%%%%%%%
\subsection{The algorithm \ap}
%%%%%%%%%%%%%%%%%%%%%

Let $V\in\set{0,1}^t$ be a vector of length $t$. The algorithm \ap takes the vector $V$ as input and returns a word $w$
avoiding $p$ and a data structure $R$ that is called a \emph{record}
in the remaining of the paper.

\begin{algorithm}
\dontprintsemicolon
\linesnumbered

\SetKwInOut{Input}{Input}\SetKwInOut{Output}{Output}
\Input{$V$.}
\Output{$w$ (a word avoiding $p$) and $R$ (a data structure).\vspace{.2cm}}

  $w\gets \epsilon$ 

  $R\gets \emptyset$
  
  \For{$i\gets 1$ \KwTo $t$}{
    Append $V[i]$ (the $i$-th letter of $V$) to $w$

    Encode in $R$ that a letter has been appended to $w$
    
    \If{$w$ contains a factor of length $\ell$ corresponding to an occurrence of $p$}{
      Encode in $R$ the occurrence of $p$

      Erase the suffix of length $\ell$ of $w$
    }
  }
  \Return $R$, $w$
  \caption{\ap\label{algo:ap}}
\end{algorithm}

The way we encode information in $R$ at lines~5
and~7 will be explained in Subsection~\ref{subsec:record}.

In the algorithm \ap, let $w_i$ be the word $w$ after $i$ steps.
Clearly, $w_i$ avoids $p$ at each step. By contradiction hypothesis,
the resulting word $w$ of the algorithm (that is $w_t$) has length less than $n$.
We will prove that each output of the algorithm allows to determine the input.
Then we obtain a contradiction by showing that the number of possible outputs
is strictly smaller than the number of possible inputs
when $t$ is chosen large enough compared to $n$.
This implies that every pattern $p$ with at most $k$ variables and length at least
$q(k)$ is $2$-avoidable.

To analyze the algorithm, we borrow ideas from graph coloring
problems~\cite{Joret:2012,Esperet:2012}. These results are based on
the Moser-Tardos~\cite{moser:2010} entropy-compression method which
is an algorithmic proof of the Lov\'asz Local Lemma.

%%%%%%%%%%%%%%%%%%%%%
\subsection{The record $R$}\label{subsec:record}
%%%%%%%%%%%%%%%%%%%%%

An important part of the algorithm is to update the record $R$ at each
step of the algorithm. Let $R_i$ be the record after $i$ steps of the
algorithm \ap. On one hand, given $V$ as input of the algorithm, this
produces a pair $(R_t,w_t)$. On the other hand, given a pair
$(R_t,w_t)$, we will show in Lemma~\ref{lem:inj} that we can recover
the entire input vector $V$. So, each input vector $V$ produces a
distinct pair $(R_t,w_t)$.
 
Let $\mathcal{V}$ be the set of input vectors $V$ of size $t$, let
$\mathcal{R}$ be the set of records $R$ produced by the algorithm \ap
and let $\mathscr{O}$ be the set of different outputs $(R_t,w_t)$.
After the execution of the algorithm ($t$ steps), $w_t$ avoids $p$ by
definition and therefore $|w_t|<n$ by contradiction hypothesis.
Hence, the number of possible final words $w_t$ is independent from
$t$ (it is at most $2^n$). We then clearly have $|\mathscr{O}| \le
2^n\times |\mathcal{R}|$. We will prove that $|\mathcal{V}|\le
|\mathscr{O}|$ and that $|\mathcal{R}|=o(2^t)$ to obtain the
contradiction $2^t=|\mathcal{V}|\le |\mathscr{O}| \le
2^n\times|\mathcal{R}|=o(2^t)$.

The record $R$ is a triplet $R=(D,L,X)$ where $D$ is a binary word
(each element is $0$ or $1$), $L$ is a vector of $(k-1)$-sets of
non-zero integers and $X$ is a binary word. At the beginning, $D$,
$L$ and $X$ are empty. At step $i$ of the algorithm, we append $V[i]$
to $w_{i-1}$ to get $w'_i$.

If $w'_i$ contains no occurrence of $p$, then we append $0$ to $D$ to
get $R_i$ and we set $w_i=w'_i$. Otherwise, suppose that $w'_i$
contains an occurrence $h$ of $p$ that forms a factor $h(p)$ of length
$\ell$, that is, the suffix of length $\ell$ of $w'_i$ is $h(p)$.
Recall that $A_j$ is the $j$-th variable of $p$. For $1\le j \le k-1$,
let $z_j=|h(A_1\ldots A_j)|$. Let $L'=\set{z_1,z_2,\ldots,z_{k-1}}$
be a $(k-1)$-set of non-zero integers.
To get $R_i$, we append the factor $01^\ell$ to $D$;
we add $L'$ as the last element of $L$;
and we append the factor $h(A_1A_2\ldots A_k)$ to $X$.
\pagebreak
\begin{exampleruled}
 Let us give an example with $k=3$, $p=ACBBCBBABCAB$
  and \linebreak
  $V=[0,0,1,0,0,1,1,0,0,1,1,1,0,0,1,1,0,1,1,1,0,0,0,1,1,0]$. The
  variables of $p$ were initially ordered as $(A,B,C)$. For the first
  $24$ steps, no occurrence of $p$ appeared, so at each step $i\le
  24$, we append $V[i]$ to $w_{i-1}$ and we append one $0$ to $D$.
  Hence, at step $24$, we have:
  \pagebreak
  \begin{itemize}
    \item $w_{24}=001001100111001101110001$ 
    \item $\displaystyle R_{24} =\left\{ 
        \begin{array}{rcl}
          D&=&000000000000000000000000=0^{24}\\ 
          L&=&[\ ]\\ 
          X&=&\epsilon
        \end{array} \right.$
  \end{itemize} 
  Now, at step $25$, we first append $V[25] = 1$ to $w_{24}$ to get $w'_{25}$.
  The word $w'_{25}$ contains an occurrence
  $h=(A\to01;B\to1;C\to100)$ of $p$ which forms a factor of length $21$ (the
  $21$ last letters of $w'_{25}$). Then we set
  $L'=\set{|h(A)|,|h(AB)|}=\set{2,3}$.
  We obtain $w_{25}$ from $w'_{25}$ by erasing its suffix of length $21$.
  To get $R_{25}$, we append the factor $01^{21}$ to $D$, we add $L'$ as the
  last element of $L$, and we append the factor $h(ABC)=011100$ to $X$.
  This gives: \newpage
  \begin{itemize}
    \item $w_{25}=0010$ 
    \item $\displaystyle R_{25} =\left\{ 
        \begin{array}{rcl}
          D&=&0000000000000000000000000111111111111111111111=0^{25}1^{21}\\ 
          L&=&[\set{2,3}] \\
          X&=&011100
        \end{array} \right.$
  \end{itemize}
\end{exampleruled}

Let $V_i$ be the vector $V$ restricted to its $i$ first elements.
We will show that the pair $(R_i,w_i)$ at some step $i$ allows to recover $V_i$.

\begin{lemma}\label{lem:inj}
  After $i$ steps of the algorithm \ap, the pair $(R_i,w_i)$ permits to recover $V_i$.
\end{lemma}

\begin{proof}
Before step 1, we have $w_0=\epsilon$, $R_0=(\epsilon,[\ ],\epsilon)$,
and $V_0=\epsilon$. Let $R_i=(D,L,X)$ be the record after step $i$, with $1\le i\le t$.

Suppose that $0$ is a suffix of $D$. This means that at step $i$,
no occurrence of $p$ was found: the algorithm appended $V[i]$
to $w_{i-1}$ to get $w_i$. Therefore $V[i]$ is the last letter of
$w_i$, say $x$. Then the word $w_{i-1}$ is obtained from $w_i$ by
erasing the last letter and the record $R_{i-1}$ is obtained from
$R_i$ by removing the suffix $0$ of $D$. We recover $V_{i-1}$ from
$(R_{i-1},w_{i-1})$ by induction hypothesis and we obtain
$V_i=V_{i-1}\cdot x$.
 
Suppose now that $01^\ell$ is a suffix of $D$. This means that
an occurrence $h$ of $p$ has been created during step $i$ such
that $|h(p)| = \ell$. Let $L'$ be the last element of $L$ which
is a $(k-1)$-set $L'=\set{z_1,z_2,\ldots,z_{k-1}}$.
By construction of $L'$, we have $|h(A_1)|=z_1$ and
$|h(A_s)|=z_s-z_{s-1}$ for $2\le s\le k-1$. We know the pattern
$p$, the total length of the factor $h(p)$ (that is $\ell$) and
the lengths of the $k-1$ first variables of $p$ in $h(p)$, so we
are able to compute $|h(A_k)|$. Now, we can parse the suffix
of length $\sum_{1\le j\le k}|h(A_j)|$ of $X$, which is the factor $h(A_1\ldots A_k)$,
to obtain the factors $h(A_1),\ldots,h(A_k)$. Thus, we have recovered the
occurrence $h$ of $p$.

Now, $w_{i-1}$ is obtained by removing the last letter
$x$ of $w_i\cdot h(p)$. This letter $x$ is $V[i]$, the letter
appended to $w_{i-1}$ at step $i$ to get $w'_i$. The record
$R_{i-1}$ is obtained from $R_i$ as follows: remove the suffix
$01^\ell$ from $D$, remove the last element of $L$, and remove the suffix
$h(A_1\ldots A_k)$ of $X$. We recover $V_{i-1}$
from $(R_{i-1},w_{i-1})$ by induction hypothesis and we obtain
$V_i=V_{i-1}\cdot x$.

\end{proof}

The previous lemma proves that distinct input vectors cannot
correspond to the same pair $(R_t,w_t)$. So we get $|\mathcal{V}|\le
|\mathscr{O}|$.

%%%%%%%%%%%%%%%%%%%%%
\subsection{Analysis of $\mathcal{R}$}
%%%%%%%%%%%%%%%%%%%%%

Now we compute $|\mathcal{R}|$. Let $R=R_t=(D,L,X)$ be a given record
produced by an execution of \ap. Let $\mathcal{D}$ be the set of such
binary words $D$. For a given $D\in \mathcal{D}$, let $\mathcal{L}_D$
be the set of such vectors of $(k-1)$-sets of non-zero integers $L$ compatible
with $D$.
Let $\mathcal{X}$ be the set of such binary words $X$.


We thus have $|\mathcal{R}|\le
|\mathcal{D}|\times\max_{D\in\mathcal{D}}|\mathcal{L}_D|\times|\mathcal{X}|$.

Let us give some useful information in order to get upper bounds on
$|\mathcal{D}|$, $|\mathcal{X}|$, and $|\mathcal{L}_D|$. The algorithm
runs in $t$ steps. At each step, one letter is appended to $w$, so
$t$ letters have been appended and therefore the number of erased
letters during the execution of the algorithm is $t-|w_t|$. At some
steps, an occurrence $h$ of $p$ appears and the factor $h(p)$ is
immediately erased. Let $m$ be the number of erased factors during the
execution of the algorithm. Let $h_i(p)$, $1\le i\le m$, be the $m$
erased factors. We have $|h_i(p)|\ge q(k)$ since each variable of $p$ is
a non-empty word and $p$ has length at least $q(k)$. Moreover, we have
$\sum_{1\le i\le m}|h_i(p)|=t-|w_t|\le t$. Each time a factor $h_i(p)$ is
erased, we add an element to $L$, so $|L|=m$. 

%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis of $\mathcal{D}$}
%%%%%%%%%%%%%%%%%%%%%

In the binary word $D$, each $0$ corresponds to an
appended letter during the execution of the algorithm and each $1$
corresponds to an erased letter. Therefore, $D$ has length $2t-|w_t|$.
Observe that every prefix in $D$ contains at least as many $0$'s as $1$'s.
Indeed, since a $1$ corresponds to an erased letter $x$, this
letter $x$ had to be added first and thus there is a $0$ before that
corresponds to this $1$. The word $D$ is therefore a partial Dyck word.
Since any erased factor $h_i(p)$ has length at least $q(k)$, any
maximal sequence of $1$'s (which is called a \emph{descent} in the
sequel) in $D$ has length at least $q(k)$. So $D$ is a partial Dyck
words with $t$ $0$'s such that each descent has length at least $q(k)$.

Let $C_{t,r,d}$ (resp. $C_{t,d}$) be the number of partial Dyck words
with $t$ $0$'s and $t-r$ $1$'s (resp. Dyck words of length $2t$) such
that all descents have length at least $d$.

\begin{lemma}\label{louis1}
  $C_{t,r,d}\le C_{t+d,d}$.
\end{lemma}

\begin{proof}
We map every partial Dyck word $y$ with $t$ $0$'s and $t-r$ $1$'s to the Dyck word $y0^d1^{d+r}$,
which has $t+d$ $0$'s and $t+d$ $1$'s. Since $d$ is fixed, this mapping is injective.
This proves the lemma.
\end{proof}

If $q(k)\ge d$, then we have $|\mathcal D|\le C_{t,|w_t|,q(k)}\le C_{t,|w_t|,d}\le C_{t+d,d}$ by Lemma~\ref{louis1}.
Let $\phi_d(x) = 1+\sum_{j\ge d}x^j = 1+\frac{x^d}{1-x}$.
The radius of convergence of $\phi_{d}$ is $1$.
The following lemma comes from a more general statement of Esperet and Parreau~\cite{Esperet:2012}
and gives an upper bound on $|\mathcal{D}|$.

\begin{lemma}\cite{Esperet:2012}\label{louis2}
  Let $d$ be an integer such that the equation $\phi_d(x)-x\phi_d'(x)=0$
  has a solution $\tau$ with $0<\tau<1$. Then $\tau$ is the unique solution of the
  equation in the open interval $(0,1)$. Moreover, there exists a
  constant $c_d$ such that $C_{t,d}\le c_d\gamma_d^tt^{-\frac{3}{2}}$
  where $\gamma_d=\phi_d'(\tau)=\frac{\phi_d(\tau)}{\tau}$.
\end{lemma}

The equation $\phi_{d}(x)-x\phi_{d}'(x)=0$
is equivalent to $P(x)=(1-x)^2+(1-d)x^{d}+(d-2)x^{d+1}=0$.
Since $P(0)=1$ and $P(1)=-1$, $P(x)=0$ has a solution $\tau$ in the open
interval $(0,1)$. By Lemma~\ref{louis2}, this solution is unique and,
for some constant~$c_{d}$, we have $C_{t+d,d}\le
c_{d}\gamma_d^{t+d}({t+d})^{-\frac{3}{2}}$ with
$\gamma_d=\phi'_{d}(\tau)$. We clearly have $C_{t+d,d}=o(\gamma_d^t)$.
So, we can compute $\gamma_d$ for $d$ fixed. We will use the following bounds:
$\gamma_{24}\le 1.27575$ and $\gamma_{48}\le 1.15685$.

So, by Lemmas~\ref{louis1} and~\ref{louis2}, when $t$ is large enough,
we have $|\mathcal{D}| < 1.27575^t$ (resp. $|\mathcal{D}| <
1.15685^t$) if the length of any descent
is at least $24$ (resp. $48$).

%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis of $\mathcal{X}$}\label{subsubsec:X}
%%%%%%%%%%%%%%%%%%%%%

Each erased factor $h_i(p)$ adds $|h_i(A_1\ldots A_k)|$ letters to $X$.
Since $p$ is doubled, we have $|h_i(p)| \ge 2|h_i(A_1\ldots
A_k)|+q(k)-2k\ge 2|h_i(A_1\ldots A_k)|+24-2\times4$. This gives
\linebreak $|h_i(A_1\ldots A_k)|\le\frac{|h_i(p)|}{2}-8$. Since
$\sum_{1\le i\le m}|h_i(p)|\le t$, we have $|X|=\sum_{1\le i\le
m}|h_i(A_1\ldots A_k)|$ $\le \sum_{1\le i\le
m}\paren{\frac{|h_i(p)|}{2}-8} \le \frac{t}2-8m$. Therefore
$|\mathcal{X}|\le 2^{\frac{t}{2}-8m+1}\le (\sqrt{2})^t$.

%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Analysis of $\mathcal{L}_D$}\label{subsubsec:LD}
%%%%%%%%%%%%%%%%%%%%%

For a given $R=(D,L,X)$, the vector $L$ is dependent on the partial
Dyck word $D$. Indeed, by construction, the $i$-th element of $L$ is a
$(k-1)$-set of integers smaller than $\frac{\ell}{2}$ where $\ell$
is the length of the $i$-th descent of $D$. In this subsection, we
compute an upper bound on the number of vectors $L$ compatible with
$D$ for a given $D\in \mathcal{D}$ and thus we give an upper bound
on $|\mathcal{L}_D|$.

Each element $L_i=\set{z_1,z_2,\ldots,z_{k-1}}$ of $L$ corresponds to
the erased factor $h_i(p)$ and by construction we have
$|h_i(A_1\ldots A_j)| = z_j$. By construction of $D$, $|h_i(p)|$ is
the length of the $i$-th descent of $D$. Since $D$ is fixed,
$|h_i(p)|$ is fixed for every $1\le i\le m$.

Let $s_k(\ell)$ be the number of such $(k-1)$-sets $L_i$ that
correspond to factors of length $\ell$. Recall that $|h_i(p)|\ge
q(k)$, so $s_k(\ell)$ is defined for $k\ge 4$ and $\ell\ge q(k)$.
Each of the $m$ elements of $L$ corresponds to an erased factor, so
$|\mathcal{L}_D|\le s_k(|h_1(p)|)\times
s_k(|h_2(p)|)\times\ldots\times s_k(|h_m(p)|)$. Let
$g_k(\ell)=s_k(\ell)^\frac{1}{\ell}$ be defined for $k\ge 4$ and
$\ell\ge q(k)$. Then $|\mathcal{L}_D|\le
g_k(|h_1(p)|)^{|h_1(p)|}\times g_k(|h_2(p)|)^{|h_2(p)|}\times
\ldots\times g_k(|h_m(p)|)^{|h_m(p)|}$. So, if we are able to
upper-bound $g_k(\ell)$ by some constant $c$ for all $\ell\ge q(k)$,
then we get $|\mathcal{L}_D|\le c^{|h_1(p)|}\times
c^{|h_2(p)|}\times\ldots\times c^{|h_m(p)|}\le c^t$.

Now we bound $g_k(\ell)$ using two different methods
depending on the number $k$ of variables in $p$ and the length $q(k)$ of $p$. 

\paragraph{Bound on $g_k(\ell)$ for $k=4$, $\ell\ge 96$\ \ or\ \ $k\ge 5$,
 $\ell\ge q(k)$}\label{par:l1}\ \medskip

As shown in Section~\ref{subsubsec:X}, we have $|h_i(A_1\ldots A_k)|\le\frac{|h_i(p)|}{2}-8$.
For a given $L_i=\set{z_1,z_2,\ldots,z_{k-1}}$ that corresponds to $h_i(p)$, we
thus have $z_{k-1} = |h_i(A_1\ldots A_{k-1})|\le\frac{|h_i(p)|}{2}-9$.
Therefore, $L_i$ is a set of $(k-1)$ distinct integers between $1$ and $\frac{|h_i(p)|}{2}-9$.
So $s_k(\ell)\le{\floor{\ell/2}\choose k-1}$ and $g_k(\ell)\le{\floor{\ell/2}\choose k-1}^{\frac{1}{\ell}}$.
We can upper-bound $g_k(\ell)$ by $\overline{g_k}(\ell)=
\paren{\frac{\paren{\ell/2}^{k-1}}{(k-1)!}}^{\frac{1}{\ell}}$
for $\ell\ge q(k)$.

Let us show that when $k$ is fixed, $\overline{g_k}(\ell)$ is a decreasing
function of $\ell$ for $\ell\ge q(k)$.
The derivative $\paren{\overline{g_k}(\ell)}'=\overline{g_k}(\ell)\times\frac1{\ell^2}\times\paren{k-1-\ln\paren{\frac{\paren{\ell/2}^{k-1}}{(k-1)!}}}$
is negative if and only if $k-1<\ln\paren{\frac{\paren{\ell/2}^{k-1}}{(k-1)!}}$, that is,
if and only if $(k-1)!e^{k-1}<\paren{\ell/2}^{k-1}$.
This inequality holds since  $(k-1)!e^{k-1}<\paren{(k-1)e}^{k-1}<\paren{3\times2^{k-2}}^{k-1}\le\paren{\ell/2}^{k-1}$.

We also have that $\overline{g_{k}}(q(k))$ is a decreasing function of $k$ for $k\ge4$
since we have checked using Maple that the only zero of its derivative is at $k\approx 3.37$ and that its derivative
is negative for $k\ge 3.38$. %So $\overline{g_{k}}(q(k))\le\overline{g_5}(48)$ for all $k\ge 5$.

Thus, we get $g_k(\ell)<\overline{g_k}(\ell)\le\overline{g_k}(q(k))\le\overline{g_5}(48) < 1.21973$ for all $k\ge 5$
and $\ell\ge q(k)$, and we get $g_4(\ell)<\overline{g_4}(\ell)\le\overline{g_4}(96) < 1.10773$ for
all $\ell\ge 96$. We chose the value $96$ to distinguish between the cases,
because it is the smallest value such that the argument holds.

\paragraph{Bound on $g_4(\ell)$ for $24\le \ell\le 95$} \label{par:l2}\ \medskip

The second method to bound the size of $g_4(\ell)$ is based on
ordinary generating functions (OGF). Here, $k=4$, so let
$A_1,A_2,A_3,A_4$ be the four variables of $p$ and let $a_i$ be the
number of instances of $A_i$ in $p$. Therefore,
$a_1+a_2+a_3+a_4=|p|$. Recall that each variable appears at least
twice in $p$ since $p$ is doubled, so $a_i\ge 2$. Moreover, a factor
of length $\ell$, with $24\le\ell\le 95$, necessarily corresponds to an occurrence
of a pattern of length between $24$ and $95$. So we just have to
consider patterns $p$ with $24\le|p|\le 95$.

Given $L_i=\set{z_1,z_2,z_3}$ an element of $L$ corresponding to
$h_i(p)$, we have $|h_i(A_1)| = z_1$, $|h_i(A_2)| = z_2-z_{1}$,
$|h_i(A_3)| = z_3-z_{2}$ and $|h_i(A_4)| =
\frac{|h_i(p)|-(a_1|h_i(A_1)|+a_2|h_i(A_2)|+a_3|h_i(A_3)|)}{a_4}$.
Let $\mathcal{A}_p=\sum_{j\ge |p|}b_j\ x^j$ be the OGF of such
sets $L'$, i.e. $b_j$ is the number of $3$-sets $\set{z_1,z_2,z_3}$
that corresponds to a factor of length $j$ formed by an occurrence of $p$.
In other words, $b_j$ is the number of
$4$-tuples $(\ell_1,\ell_2,\ell_3,\ell_4)$ such that $a_1\times
\ell_1+ a_2\times \ell_2+ a_3\times \ell_3+a_4\times \ell_4=j$ and
with $\ell_i\ge 1$ (since each variable of $p$ corresponds to a
non-empty word). So by definition of $h_4$, we have $h_4(\ell)=b_\ell$
and thus $g_4(\ell)=b_\ell^{\ \frac{1}{\ell}}$.

This kind of OGF has been studied and is similar to the well-known
problem of counting the number of ways you can change a
dollar~\cite{polya:1983}: you have only five types of coins (pennies,
nickels, dimes, quarters, and half dollars) and you want to count the
number of ways you can change any amount of cents. So, let
$\mathcal{C}=\sum_{j\ge 1}c_j\ x^j$ be the OGF of the problem and thus
any $c_j$ is the number of ways you can change $j$ cents. Then, for example,
$c_{100}$ corresponds to the number of ways you can change a
dollar. Here, $\mathcal{C}=\frac{1}{1-x}\times \frac{1}{1-x^5}\times
\frac{1}{1-x^{10}}\times \frac{1}{1-x^{25}}\times \frac{1}{1-x^{50}}$.

In our case, we have four coins with value $a_1$, $a_2$, $a_3$, and
$a_4$ respectively (so we can have different types of coins with the
same value) and each type of coins appears at least once (since
$\ell_i\ge 1$). Thus we get $\mathcal{A}_p=\sum_{j\ge |p|}b_j\ x^j
= \frac{x^{a_1}}{1-x^{a_1}}\times\frac{x^{a_2}}{1-x^{a_2}}
\times\frac{x^{a_3}}{1-x^{a_3}}\times\frac{x^{a_4}}{1-x^{a_4}}$. We
use Maple for our computation. For each $24\le |p|\le 95$, for each
$4$-tuple $(a_1,a_2,a_3,a_4)$ such that $\sum a_i = |p|$, we consider
the associated OGF $\mathcal{A}_p$ and we compute, using Maple,
the truncated series expansion up to the order $95$, that gives
$\mathcal{A}_p = b_{24} x^{24} + b_{25} x^{25} + \ldots + b_{95}
x^{95} + O(x^{96})$ with explicit values for the coefficients $b_j$.
So, for any $24\le \ell\le 95$, $g_4(\ell)$ is upper-bounded by the
maximum of $b_\ell^{\ \frac{1}{\ell}}$ taken over all
$\mathcal{A}_p$. Maple gives that $b_\ell^{\ \frac{1}{\ell}}$ is
maximal for $|p|=24$, $(a_1,a_2,a_3,a_4) = (2,2,2,18)$, and $\ell=46$:
in this case, $b_{46}=84$ (i.e. there exist $84$ distinct $3$-sets
$L_i$ that correspond to some factor of length $46$ formed by an
occurrence of a pattern of length $24$ where three variables
appear twice and one variable appears $18$ times). So, $g_4(\ell)\le
84^\frac{1}{46}< 1.10112$ for all $24\le \ell\le 95$.

\paragraph{Bound on $g_k(\ell)$ for all $k\ge 4$}\ \medskip

We can deduce from Paragraphs~\ref{par:l1} and~\ref{par:l2} the
following.

If $k=4$, then $g_4(\ell)< 1.10112$ for $24\le\ell\le 95$ and
$g_4(\ell)< 1.10773$ for $\ell\ge 96$. So for $k=4$, we have
$|\mathcal{L}_D|< (1.10773)^t$.

If $k\ge 5$, then $g_k(\ell)< 1.21973$ for $\ell\ge q(k)$.
So for $k\ge 5$, we have $|\mathcal{L}_D|< (1.21973)^t$.

%%%%%%%%%%%%%%%%%%%%%
\subsection{End of the proof}
%%%%%%%%%%%%%%%%%%%%%

The bounds on
$|\mathcal{L}_D|$ obtained in Subsection~\ref{subsubsec:LD}  hold for any
fixed $D\in \mathcal{D}$. So they also hold for
$\max_{D\in\mathcal{D}}|\mathcal{L}_D|$.

Aggregating the above analysis, we get the following.
For $k\ge 5$, we have $q(k)\ge 48$: then $|\mathcal{R}|\le
|\mathcal{D}|\times\max_{D\in\mathcal{D}}|\mathcal{L}_D|\times|\mathcal{X}|\le (1.15685\times
1.21973\times\sqrt{2})^t =o(2^t)$. For $k=4$, we have $q(k)\ge 24$:
then
$|\mathcal{R}|\le|\mathcal{D}|\times\max_{D\in\mathcal{D}}|\mathcal{L}_D|\times|\mathcal{X}|
\le(1.27575\times1.10773\times\sqrt{2})^t = o(2^t)$.

Thus for all $k\ge 4$, $|\mathcal{R}| = o(2^t)$ and so we obtain the
desired contradiction: $$2^t=|\mathcal{V}|\le |\mathscr{O}| \le 2^n\times|\mathcal{R}|= 2^n
\times o(2^t)=o(2^t).$$

%%%%%%%%%%%%%%%%%%%%%
\section{Conclusion}
%%%%%%%%%%%%%%%%%%%%%

In our results, we heavily use the fact that the patterns are doubled.
The fact that the patterns are long is convenient for our proofs but
does not seem so important. So we ask whether every doubled pattern
is 3-avoidable. By the remarks in Section~\ref{sec:intro} and by
Lemma~\ref{k6doubled}, the only remaining cases are doubled patterns
with $4$ and $5$ variables. Also, does there exist a finite $k$
such that every doubled pattern with at least $k$ variables is
2-avoidable ? Using the standard backtracking algorithm, we have
checked by computer that ABCCBADD is not 2-avoidable.
So we know that such a $k$ is at least 5.

%%%%%%%%%%%%%%%%%%%%%%%
\subsection*{Acknowledgments}
%%%%%%%%%%%%%%%%%%%%%%%

We are grateful to the anonymous referees for their helpful suggestions
to improve the presentation of the paper.

\begin{thebibliography}{10}

\bibitem{BEM79} D.R.~Bean, A.~Ehrenfeucht, and G.F.~McNulty,
Avoidable Patterns in Strings of Symbols,
{\em Pacific J. of Math.} {\bf 85} (1979) 261--294.

\bibitem{BellGoh:2007} J.~Bell, T. L.~Goh.
Exponential lower bounds for the number of words of uniform length avoiding a pattern,
\emph{Inform. and Comput.} {\bf 205}
(2007), 1295-1306.

\bibitem{Berstel92} J.~Berstel.
\newblock Axel {T}hue's work on repetitions in words.
\newblock Invited Lecture at the 4th Conference on Formal Power Series and
 Algebraic Combinatorics, Montreal, 1992, June 1992.
\newblock Available at \url{http://www-igm.univ-mlv.fr/~berstel/index.html}.

\bibitem{Blanchet:2013} F. Blanchet-Sadri,  B. Woodhouse.
\newblock Strict Bounds for Pattern Avoidance.
\newblock \emph{Theor. Comput. Sci.} {\bf 506} (2013), 17--27.

\bibitem{Cassaigne:1994} J.~Cassaigne.
Motifs \'evitables et r\'egularit\'e dans les mots,
Th\`ese de Doctorat, Universit\'e Paris VI, Juillet 1994.

\bibitem{Joret:2012} V.~Dujmovi\'c, G.~Joret, J.~Kozik, and D.~R.~Wood.
\newblock Nonrepetitive Colouring via Entropy.
\newblock {\em Combinatorica}, to appear, 2013+ (Also available on \arxiv{1112.5524}).

\bibitem{Esperet:2012} L.~Esperet and A. Parreau.
\newblock Acyclic edge-coloring using entropy compression.
\newblock \emph{European Journal of Combinatorics} {\bf36(4)} (2013), 1019--1027.

\bibitem{Lothaire:2002} M.~Lothaire.
\newblock Algebraic Combinatorics on Words.
\newblock \emph{Cambridge Univ. Press} (2002).

\bibitem{moser:2010} R.~A.~Moser, G.~Tardos. 
\newblock A constructive proof of the general Lovasz local lemma.
\newblock {\em J. ACM}, {\bf 57(2)} (2010), p. 11:1-11:15.

\bibitem{Ochem:2004} P.~Ochem.
\newblock A generator of morphisms for infinite words.
\newblock \emph{RAIRO: Theoret. Informatics Appl.} {\bf 40} (2006) 427--441.

\bibitem{polya:1983}
G.~P\'olya, R.~E.~Tarjan, D.~R.~Woods.
\newblock Notes on Introductory Combinatorics.
\newblock {\em Progress in Computer Science}, Birkhäuser (1983).

\bibitem{Rampersad:2011} N.~Rampersad.
\newblock Further applications of a power series method for pattern avoidance.
\newblock \emph{Electron. J. Combinatorics.} {\bf 18(1)} (2011), \#P134.

\bibitem{Roth:1992} P.~Roth.
\newblock Every binary pattern of length six is avoidable on the two-letter alphabet.
\newblock \emph{Acta Inform.} {\bf 29} (1992), 95--107.

\bibitem{Thue06} A.~Thue.
\newblock \"{U}ber unendliche {Z}eichenreihen.
\newblock {\em Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania}, 7:1--22, 1906.

\bibitem{Thue12} A.~Thue.
\newblock \"{U}ber die gegenseitige {L}age gleicher {T}eile gewisser {Z}eichenreihen.
\newblock {\em Norske Vid. Selsk. Skr. I. Mat. Nat. Kl. Christiania}, 10:1--67, 1912.

\bibitem{Zimin} A.I.~Zimin.
\newblock Blocking sets of terms.
\newblock {\em Math. USSR Sbornik} {\bf 47(2)} (1984) 353--364. English translation.

\end{thebibliography}

\end{document}