%&LaTeX \documentclass[12pt,a4paper,twoside]{article} \usepackage{amssymb} \author{Arturo Carpi \and Aldo de Luca} \title{Words and Repeated Factors} \date{} \pagestyle{myheadings} \markboth{A.~Carpi and A.~de Luca}{Words and Repeated Factors} %theorem-like envs \newtheorem{lemma}{Lemma} \newtheorem{thm}{Theorem} \newtheorem{prop} {Proposition} \newtheorem{corol}{Corollary} \newtheorem{defin}{Definition} \newtheorem{xmpl}{Example} \newtheorem{rmrk}{Remark} \newenvironment{example} {\begin{xmpl}\begin{normalfont}}{\end{normalfont}\end{xmpl}} \newenvironment{remark} {\begin{rmrk}\begin{normalfont}}{\end{normalfont}\end{rmrk}} %labels of enumerate env \def\labelenumi{\normalfont{(\roman{enumi})}} %proofend \newcommand{\finedim}{\hfill\raisebox{3.3pt}{\fbox{}}\par\addvspace% {\bigskipamount}} %more math functions \newcommand{\card}{\mathop{\mathrm{Card}}\nolimits} \newcommand{\alfa}{\mathop{\mathrm{alph}}\nolimits} \newcommand{\pref}{\mathop{\mathrm{Pref}}\nolimits} \newcommand{\suff}{\mathop{\mathrm{Suff}}\nolimits} \newcommand{\fact}{\mathop{\mathrm{Fact}}\nolimits} \newcommand{\dom} {\mathop{\mathrm{dom} }\nolimits} \newcommand{\ind} {\mathop{\mathrm{ind} }\nolimits} \begin{document} \maketitle \begin{abstract} In this paper we consider sets of factors of a finite word which permit us to reconstruct the entire word. This analysis is based on the notion of \emph{box}. The \emph{initial} (resp. \emph{terminal}) \emph{box} of $w$ is the shortest prefix (resp. suffix) of $w$ which is an unrepeated factor. A factor $u$ of $w$ is a \emph{proper box} if there are letters $a,a',b,b'$ with $a'\neq a$, $b'\neq b$ such that $u=asb$ and $a's$, $sb'$ are factors of $w$. A box is called \emph{maximal} if it is not a proper factor of another box. The main result of the paper is the following theorem (\emph{maximal box theorem}): \emph{Any finite word $w$ is uniquely determined by the initial box, the terminal box and the set of maximal boxes}. Another important combinatorial notion is that of \emph{superbox}. A superbox is any factor of $w$ of the kind $asb$, with $a,b$ letters, such that $s$ is a repeated factor, whereas $as$ and $sb$ are unrepeated factors. A theorem for superboxes similar to the maximal box theorem is proved. Some algorithms allowing us to construct boxes and superboxes and, conversely, to reconstruct the word are given. An extension of these results to languages is also presented. \end{abstract} \section{Introduction} The study of the factors of finite as well as infinite words represents a topic of great interest in combinatorics on words. The number of factors of any length of a word (subword complexity) has been viewed as an evaluation of the richness of the structure of the considered word. However, for a finite word, it is sufficient to know its factors up to a certain length to reconstruct the entire word. For instance, it is easily seen that the only word whose factors of length 2 are $ab$, $bc$ and $cd$ is $abcd$. The problem of reconstructing a word by knowing its `short' factors appears in several fields. For instance, in analyzing DNA molecules, it is not possible to read the entire sequence of bases but only segments of limited length. The aim of this paper is to study some sets of `short' factors of a word which completely characterize the word itself, as well as the methods to reconstruct the word from such factors. There are two combinatorial properties of factors of a word which turn out to be crucial for our purpose, namely \emph{repetition} and \emph{extendability}. Indeed, we shall show that the \emph{special factors} (see e.g. \cite{BMR,CASSA,DM,DELIMI,DELVA,DELV}), the shortest unrepeated initial and terminal factors and some related concepts are of fundamental importance in determining the `structure' of the word itself. We recall that a factor $u$ of a finite word $w$ is called \emph{right} (resp. \emph{left}) \emph{special} if there exist two distinct extensions on the right (resp. on the left) in factors of $w$. A factor is \emph{bispecial} if it is right and left special. We shall introduce two classes of factors of a word, both of which uniquely determine the word. The first one is constituted by the \emph{boxes}: the \emph{initial} and \emph{terminal box} of a word $w$ are, respectively, the shortest prefix and suffix of $w$ which are unrepeated factors while a \emph{proper box} is any factor of $w$ of the kind $asb$ with $a$ and $b$ letters and $s$ a bispecial factor of $w$. The second one is the set of the \emph{superboxes}, which are factors of $w$ of the kind $asb$ with $a$ and $b$ letters, $s$ a repeated factor of $w$ and $as, sb$ unrepeated factors of $w$. In Sec.~\ref{STRE} we prove the surprising result, called the \emph{maximal box theorem} (cf. Theorem \ref{boxthm}), that any word is completely determined by the set of its (maximal) boxes and the initial and terminal boxes. A simple procedure to construct the word from the boxes is also given. A remarkable corollary is the following. Let $K_f$ be the length of the terminal box of a word $f$ and $R_f$ be the minimal integer such that there are no right special factors of $f$ of length $R_f$. If $g$ is a word having the same set of factors as $f$ up to the length $n = \max\{R_f,K_f\}+1$, then $f=g$. The value of $n$ is \emph{optimal} since one can prove that there exists a word $g'$ having the same set of factors of $f$ up to the length $n-1$, and, moreover, all the factors of $f$ of length $n$ are factors of $g'$ and all the factors of $g'$ of length $n$ with the exception of one, are factors of $f$. In Sec.~\ref{SQUATTRO} we study some interesting structural properties of boxes. In particular it is shown that the set of the maximal boxes in Theorem \ref{boxthm}, is `nearly' optimal because for any given word $w$ one can construct another word $v$ with the property that all boxes of $w$ are factors of $v$, whereas there exist at most two boxes of $v$ which are not factors of $w$. Moreover, we show that, starting from the set of maximal boxes of a word, one can construct the so-called `reduced sets'. An analog of the maximal box theorem for reduced sets holds. These sets are convenient, since they provide a simpler representation of the word. In Sec.~\ref{SSETTE} the notion of \emph{superbox} is studied. We prove a theorem showing that the initial and terminal boxes and the set of superboxes determine uniquely the word $w$. Moreover, we give two simple algorithms: the first allows us for any word $w$ to determine the set of all superboxes and the second permits us to reconstruct the word starting from the set of all superboxes and the initial and terminal boxes. In Sec.~\ref{sec.languages} we deal with languages and a box theorem for languages is presented. As a consequence of this result, we give a new proof of the Fine and Wilf `uniqueness theorem' for periodic functions in the discrete case. \section{Preliminaries} \label{Preliminaries} Let $A$ be a finite non-empty set or \emph{alphabet} and $A^*$ the free monoid generated by $A$. The elements of $A$ are usually called \emph{letters} and those of $A^*$ \emph{words}. The identity element of $A^*$ is called \emph{empty word} and denoted by $\epsilon$. We set $A^+ = A^*\setminus \{\epsilon\}$. A word $w\in A^+$ can be written uniquely as $w = w_1 w_2 \cdots w_n$, with $w_i\in A$, $1 \leq i \leq n$, $n > 0$. The integer $n$ is called the \emph{length} of $w$ and denoted $|w|$. The length of $\epsilon$ is 0. For any $n\geq 0$, we denote by $A^n$ the set of all the words of $A^*$ of length $n$ and set $A^{[n]} = \bigcup_{i=0}^n A^n$. Let $w\in A^*$. The word $u\in A^*$ is a \emph{factor} (or \emph{subword}) of $w$ if there exist $p,q\in A^*$ such that $w = puq$. A factor $u$ of $w$ is called \emph{proper} if $u \neq w$. If $w = uq$, for some $q\in A^*$ (resp. $w = pu$, for some $p\in A^*$), then $u$ is called a \emph{prefix} (resp. a \emph{suffix}) of $w$. For any $w\in A^*$, we denote respectively by $F(w)$, $\pref(w)$ and $\suff(w)$ the sets of its factors, prefixes and suffixes. We shall denote $F(w)\cap A$ by $\alfa(w)$. This set represents the subset of the letters of $A$ occurring in the word $w$. For any $X\subseteq A^*$, we set \[ F(X) = \bigcup_{u\in X}F(u). \] An element of $F(X)$ will be also called a \emph{factor} of $X$. Let $u\in F(w)$. Any pair $(\lambda , \mu)\in A^* \times A^*$ such that $w = \lambda u \mu$ is called an \emph{occurrence} of $u$ in $w$. If $\lambda = \epsilon$ (resp. $\mu = \epsilon$), then the occurrence of $u$ is called \emph{initial} (resp. \emph{terminal}). An occurrence is called \emph{internal} if it is neither initial nor terminal. An occurrence $(\lambda , \mu)$ of $u$ in $w$ is called \emph{leftmost} (resp. \emph{rightmost}) if the length of $\lambda$ (resp. $\mu$) is minimal. A factor $u$ of $w$ is called \emph{internal} if there exists an internal occurrence of $u$ in $w$. Let $w = w_1w_2\cdots w_n$ ($w_i\in A,\ 1\leq i \leq n$) be a word on the alphabet $A$. A set $\mathcal{C} \subseteq F(w)$ is a \emph{covering} of $w$ if, for any $k= 1,\ldots ,n$, there exist $i,j$, $1\leq i\leq k\leq j\leq n$, such that $w_i w_{i+1} \cdots w_j\in\mathcal{C}$. Let us suppose $\card(A) = d$ and consider in $A^*$ the prefix ordering of the words. It is well known that the graph associated with this order is a $d$-ary tree $T_d$, whose nodes represent the words of $A^*$ and the root represents the empty word. With each finite word $w$, one can associate a finite subtree $T_w$ of $T_d$ obtained by taking all the nodes which represent factors of the word $w$. We call $T_w$ the \emph{factor tree} of $w$, since any factor of $w$ will be represented by a node $n$ of $T_w$ or, equivalently, by a unique path going from the root to the node $n$. If one replaces the prefix ordering of words by the suffix ordering one can construct in a similar way another tree $T'_w$, whose nodes represent the factors of $w$. \section{Repeated factors} \label{sec.repeated} A factor $u$ of a word $w$ is called \emph{repeated} if there are at least two distinct occurrences of $u$ in $w$. In the opposite case, the factor $u$ is called \emph{unrepeated}. A factor $u$ of $w$ is \emph{extendable} on the right (resp. left) in $w$ if there exists a letter $x \in A$ such that $ux \in F(w)$ (resp. $xu\in F(w)$). The factor $ux$ (resp. $xu$) of $w$ is called a \emph{right} (resp. \emph{left}) \emph{extension} of $u$ in $w$. If $u$ is a factor of $w$, then the \emph{right} (resp. \emph{left}) \emph{valence} of $u$ is the integer $\card(\{x \in A \mid ux \in F(w)\})$ (resp. $\card(\{x \in A \mid xu \in F(w)\})$). The right (resp. left) valence of $u$ is then the number, possibly 0, of all the distinct right (resp. left) extensions of $u$ in $w$. In terms of the factor tree $T_w$ (resp. $T'_w$) the right (resp. left) valence of $u$ is the degree (that is the number of sons) of the node representing the factor $u$. With each word $w\in A^*$ one can associate the factor $k_w$ defined as the shortest suffix of $w$ which is an unrepeated factor of $w$. This is also equivalent to say that $k_w$ is the shortest factor of $w$ which cannot be extended on the right in $w$, i.e. it has right valence equal to 0. The set of the factors of $w$ which are not extendable on the right is given by $A^*k_w \cap \suff(w)$. In the factor tree $T_w$, these factors are represented by the leaves. In a symmetric way, one can define $h_w$ as the shortest prefix of $w$ which cannot be extended on the left in $w$. Also in this case, the factors of $w$ which are not extendable on the left are represented by the leaves of the tree $T'_w$. In the following, we shall set $K_w=|k_w|$ and $H_w=|h_w|$. If $w \neq \epsilon$, then one has $1\leq K_w\leq |w|$ and $1\leq H_w\leq |w|$. If $w=\epsilon$, then $H_{\epsilon}=K_{\epsilon}=0$. One can remark that all the proper prefixes of $h_w$ and all the proper suffixes of $k_w$ are repeated factors, while $h_w$ and $k_w$ are unrepeated. In the following, for $w\neq\epsilon$, we shall denote by $h'_w$ (resp. $k'_w$) the prefix (resp. suffix) of $w$ of length $H_w-1$ (resp. $K_w-1$). A word $s$ is called a \emph{right} (resp. \emph{left}) \emph{special factor} of $w$ if there exist two letters $x,y \in A$, $x\neq y$, such that $sx,sy \in F(w)$ (resp. $xs,ys \in F(w)$). A right (resp. left) special factor of $w$ is then a repeated factor having at least two distinct extensions on the right (resp. left) in $w$, i.e. it has a right (resp. left) valence $\geq 2$. This implies that a right (resp. left) special factor of $w$ has at least an internal occurrence in $w$. We remark that the set of right (resp. left) special factors is closed by suffixes (resp. prefixes). A factor of $w$ which is right and left special is called \emph{bispecial}. Let us remark that the empty word $\epsilon$ is always a bispecial factor of $w$, except when $w$ is a power of a single letter. In such a case, $w = k_w = h_w$. We denote by $R_w$ (resp. $L_w$) the minimal non-negative integer such that there are no right (resp. left) special factors of length $R_w$ (resp. $L_w$). One has $0\leq R_w, L_w\leq |w|-1$. Since the set of right special factors is closed by suffixes, there are no right special factors of length larger than $R_w$. Symmetrically, there are no left special factors of length larger than $L_w$. A repeated factor of a word $w$ is called \emph{maximal} (with respect to the factorial order) if it is not a proper factor of another repeated factor of $w$. \begin{prop} \label{prop4} If a repeated factor $u$ of a word $w$ is maximal, then one of the following conditions is satisfied: \begin{enumerate} \item $u$ is a bispecial factor, \item $u = h'_w$, \item $u = k'_w$. \end{enumerate} \end{prop} % \emph{Proof.} Let us first suppose that $u$ is a prefix of $w$. Since $u$ is a repeated factor, then $u$ has to be a prefix of $h'_w$. From the maximality, it follows that $u = h'_w$. In a symmetric way, one proves that if $u$ is a suffix of $w$, then $u = k'_w$. Let us then suppose that $u$ is neither a prefix nor a suffix of $w$. Then, since $u$ is repeated, there will exist two internal occurrences of $u$ in $w$, and then letters $x,x',y,y'\in A$ such that $xuy,\ x'uy'$ are two different occurrences of factors of $w$. Since $u$ is a maximal repeated factor, it follows $x\neq x'$ and $y\neq y'$. Hence, $u$ is a bispecial factor of $w$. \finedim Let $w\in A^*$ be a non-empty word. We denote by $G_w$ the maximal length of a repeated factor of $w$. The following proposition, whose proof we omit for the sake of brevity, holds \cite{special,adl98}. \begin{prop} \label{prop1} Let $w\in A^+$. One has \[ G_w = \max\{R_w, K_w\} - 1 = \max\{L_w, H_w\} - 1. \] \end{prop} Let us now for any word $w\in A^*$ introduce an important set of factors that we call boxes. Let $w \in A^*$ be a word. A factor $f$ of $w$ is called a \emph{proper box} of $w$ if $f = asb$ with $a,b \in A$ and $s$ is a bispecial factor. The factor $h_w$ (resp. $k_w$) is called the \emph{initial} (resp. \emph{terminal}) \emph{box} of $w$. By \emph{box}, without specification, we mean indifferently the initial, the terminal or a proper box. A box is called \emph{maximal} (with respect to the factorial order) if it is not a proper factor of another box. The set of maximal boxes of $w$ will be denoted by $\mathcal{B}_w$. We note that, for any word, the initial, the terminal and the maximal boxes can be constructed by a simple algorithm, whose description is omitted. \section{Maximal box theorem} \label{STRE} In this section we prove a theorem, called the `maximal box theorem', which shows that if of a given word one knows the initial box, the terminal box and the set of the maximal boxes, then the word is uniquely determined. A simple procedure in order to reconstruct the word from the boxes is also given. A remarkable consequence of this theorem is that if two words $f$ and $g$ have the same set of factors up to the length $n=\max\{R_f,K_f\}+1$, then $g=f$. We prove also that this value of $n$ is optimal. \begin{lemma} \label{lemma1} Let $\alpha$ be a box of $w$. Then any internal factor of $\alpha$ is repeated in $w$. \end{lemma} % \emph{Proof.} Let us first suppose that $\alpha = k_w$ and $f$ is an internal factor of $\alpha$. One has that $f$ is a factor of $k'_w$, so that it is repeated in $w$. In a symmetrical way, one reaches the same result if $f$ is an internal factor of $\alpha = h_w$. Let us now suppose that $\alpha = asb$ is a proper box of $w$. An internal factor $f$ of $\alpha$ is a factor of $s$, which is a bispecial factor of $w$. Since $s$ is a repeated factor of $w$, so will be $f$. \finedim \begin{example} \label{esempio1} Let $w$ be the word $ w = abccbabcab$. One has $h_w = abcc$, $k_w = cab$. The proper boxes of $w$ are $ab$, $ba$, $bc$, $ca$, $cb$, $cc$, $abc$, $bca$, $bcc$, $cba$, $ccb$. The maximal boxes are \[ abcc,\quad bca,\quad cab,\quad cba,\quad ccb. \] Let $w=abaababaaba$. In this case $h_w=abaabab$, $k_w=babaaba$ and these are the only maximal boxes of $w$. \end{example} For all $n\geq 0$, we introduce the binary relation $\preceq_n$ in $A^*$ defined as: for $f, g \in A^*$, \[ f \preceq_n g \quad \mbox{if and only if} \quad F(f)\cap A^{[n]} \subseteq F(g)\cap A^{[n]}. \] One easily verifies that the relation $\preceq_n$ is a well-founded quasi-order and, for all $f,u,v\in A^*$, $n \ge 0$, one has $f \preceq_n ufv$. We note that the intersection of the $\preceq_n$ for all $n \geq 0$ is the factorial order, that we denote by $\preceq$. For all $n\geq 0$, we consider the equivalence relation $\sim_n\ =\ \preceq_n\ \cap\ {\preceq_n}^{-1}$. Thus \[ f \sim_n g \quad \mbox{if and only if} \quad F(f)\cap A^{[n]} = F(g)\cap A^{[n]}. \] \begin{thm} \label{boxthm} \emph{(Maximal box theorem)} Let $f,g \in A^*$ be two words such that \begin{enumerate} \item \label{cond1} $h_f = h_g, \quad k_f = k_g$, \item \label{cond2} $\mathcal{B}_f \subseteq F(g)$, \item \label{cond3} $\mathcal{B}_g \subseteq F(f)$. \end{enumerate} Then $f = g$. \end{thm} % \emph{Proof.} We prove, by induction, that for all $n\geq 0$, $f\sim_n g$. Clearly, this implies that $f=g$. Let us prove first the base of the induction, i.e. $f\sim_1 g$. If $\card(\alfa(f)) \leq 1$, then $f = k_f = k_g$. Thus, $f \in F(g)$. Let us then suppose $\card(\alfa(f)) > 1$. In such a case, $\epsilon$ is a bispecial factor and any $w \in A^2 \cap F(f)$ is a box. Since $w$ is included in a maximal box, one has $w \in F(g)$. Thus we have $f \preceq_1 g$. In a symmetrical way, one proves that $g \preceq_1 f$. Now, let us prove the induction step. We suppose that $n \geq 1$, $f\sim_n g$ and prove that $f\sim_{n+1} g$. Let $w$ be a factor of $f$ of length $n+1$. If $w$ is a box of $f$, then $w$ is a factor of a maximal box and, therefore, by condition (ii), $w$ is a factor of $g$. Let us then suppose that $w$ is not a box. We factorize $w$ as $w = atb$, with $a,b\in A$, $t\in A^*$, and $t$ is not a bispecial factor of $f$. Since $|at| = |tb| = n$, by the inductive hypothesis, one has that $at,tb\in F(g)$. Let us first suppose that $t$ is not a right special factor of $f$. Since $at$ is extendable on the right in $f$, $k_g = k_f$ cannot be a suffix of $at$. This implies that $at$ can be extended on the right in $g$. Thus there exists a letter $c$ such that $atc \in F(g)$. By the inductive hypothesis, $tc \in F(f)$. Since $t$ is not right special in $f$, one obtains $b = c$ and then $atb \in F(g)$. With a symmetrical argument, if $t$ is not a left special factor of $f$, one proves again that $atb \in F(g)$. Thus we have obtained that $f \preceq_n g$. In a symmetrical way, one derives that $g \preceq_n f$. \finedim \begin{prop} \label{bprop} Let $w$ be a word. If $v$ is a factor of $w$, then there exists $u\in\suff(v)$ such that for any $a\in A$ \begin{equation} va\in F(w)\quad \mbox{if and only if} \quad (ua\in F(\mathcal{B}_w)\mbox{ and } va\not\in A^+h_w). \label{eq:extend} \end{equation} \end{prop} % \emph{Proof.} If $v$ is not right extendable, then the statement is trivially verified by $u=v$. If $\card(\alfa(w))=1$, then the statement is verified by $u=\epsilon$, since in this case $h_w=w$. If $v=\epsilon$, then $u=\epsilon$ satisfies the condition. Let us then suppose that $v\neq \epsilon$ is right extendable and that $\card(\alfa(w))$ $>1$. We can write \[ v=\lambda bs,\quad b\in A,\ \lambda \in A^*, \] where $s$ is the longest proper suffix of $v$ which is a bispecial factor of $w$. We set $u=bs$. Let $a$ be a letter of $A$ and suppose $va\in F(w)$. This trivially implies that $va\not\in A^+h_w$. Moreover, $ua=bsa$ is a box so that $ua\in F(\mathcal{B}_w)$. Conversely, let $ua\in F(\mathcal{B}_w)$, $va\not\in A^+h_w$ and suppose, by contradiction, that $va\not\in F(w)$. Let $t$ be the longest suffix of $v$ such that $ta\in F(w)$. Since $t\neq v$, one can write \[ v = \mu c t, \mbox{ with }c\in A,\ \mu \in A^*\ \mbox{and}\ cta\not\in F(w). \] Since $va\not\in A^+h_w$, it follows that $ta\neq h_w$. Thus, since $t$ is left extendable in $w$, one derives that $ta$ is left extendable in $w$, so that there exists a letter $x\in A$ such that $xta\in F(w)$. Moreover, since $v$ is right extendable in $w$, there exists a letter $y\in A$ such that $cty\in F(w)$. One has $x\neq c$ and $y\neq a$, since $cta\not\in F(w)$. Hence, $t$ is bispecial. This contradicts the fact that $|t|\geq|u|>|s|$. \finedim The previous proposition shows that if $v$ is a right extendable factor of $w$, then to find a right extension of $v$ it is sufficient to determine the longest suffix $u$ of $v$ in $w$ such that there is at least one letter $a\in A$ satisfying the right hand side condition of Eq.~(\ref{eq:extend}). For such a letter $a$ one has $va\in F(w)$. Let us now give a simple procedure, based on Proposition \ref{bprop}, which allows us to construct the word $w$ knowing the initial box $h_w$, the terminal box $k_w$ and the set $\mathcal{B}_w$ of maximal boxes. Let us write $h_w=h'_wz$, with $z\in A$. Initially, we set $p=h_w$. Now suppose that we have already constructed a prefix $p$ of $w$ of length $|p|\geq H_w$. If $p\in A^*k_w$, then the procedure ends and $w=p$. Otherwise, the right valence of $p$ is 1. In order to extend $p$ in $w$, we have to distinguish the following cases: \medskip (i) $p\not\in A^*h'_w$. \medskip\noindent In this case, we search for the shortest suffix $u$ of $p$ which can be extended on the right in $F(\mathcal{B}_w)$ by a unique letter $x$ and replace $p$ by $px$. Indeed, by Proposition \ref{bprop}, there exists a suffix of $p$ which can be extended on the right in $F(\mathcal{B}_w)$ by a unique letter which is exactly the letter extending $p$ on the right in $w$. \medskip (ii) $p\in A^*h'_w$. \medskip\noindent In this case, we search for the shortest suffix $u$ of $p$ which can be extended on the right in $F(\mathcal{B}_w)$ by a unique letter $x\in A\setminus \{z\}$ and replace $p$ by $px$. Indeed, by Proposition \ref{bprop}, there exists a suffix of $p$ which can be extended on the right in $F(\mathcal{B}_w)$ by a unique letter in the set $A\setminus \{z\}$ which is exactly the letter extending $p$ on the right in $w$. \begin{prop} \label{prop3} Let $f\in A^*$ and $n = R_f+1$. If $g\in A^*$ is such that $g \sim_n f$ and $k_f = k_g$, then $f = g$. \end{prop} % \emph{Proof.} Let us first prove that $R_f=R_g$. By the hypothesis, $f$ and $g$ have the same set of factors up to the length $n = R_f+1$, so that all right special factors of $f$ are also right special factors of $g$. Thus $R_f \leq R_g$. Let us suppose that $R_f < R_g$. Since the right special factors are closed by suffixes, there exists a right special factor of $g$ of length $R_f$. This is also a right special factor of $f$, since $f \sim_{R_f+1} g$, and this is a contradiction. Thus $R_f = R_g = R$. Remark that the length of any proper box of $f$ or of $g$ is at most $n$. Indeed, any proper box of $f$ (resp. of $g$) can be written as $asb$ with $a,b\in A$ and $s$ a bispecial factor of $f$ (resp. of $g$). This implies that $|asb|\leq R+1$. Hence, by the hypothesis that $g \sim_n f$, one derives that any proper maximal box of $f$ is a factor of $g$ and, conversely, any proper maximal box of $g$ is a factor of $f$. Since $k_f = k_g$, in view of Theorem \ref{boxthm}, in order to prove $f = g$, it is sufficient to show that $h_f = h_g$. Let us first suppose that $|h_f| \leq R$. Then $h_f$ is a factor of $g$ which cannot be extended on the left in $g$ because $f\sim_n g$. Thus $h_g$ has to be a prefix of $h_f$. This implies $|h_g| \leq R$, so that, by using the same argument, it follows that $h_f$ has to be a prefix of $h_g$, and then $h_f = h_g$. By a symmetrical argument, one arrives to the same conclusion if one supposes that $|h_g| \leq R$. Hence, we may suppose that $|h_f|,|h_g| > R$. This implies that $h'_f$ (resp. $h'_g$) is not a right special factor of $f$ (resp. $g$). Let us show that $h'_f$ cannot be an internal factor of $f$. Indeed, otherwise there would exist letters $x,y\in A$ such that $h_f=h'_f x$ and $h'_fy\in F(f)$. Since $h_f$ is unrepeated then $x\neq y$ so that $h'_f$ would be a right special factor of $f$. Thus, $h'_f$ has to be a suffix of $k'_f$. Since $k'_f$ is repeated, and $h'_f$ is not an internal factor of $f$, the only possibility is that $h'_f=k'_f$. In a similar way, one has that $h'_g=k'_g$. By the hypothesis that $k_f=k_g$, one derives $h'_f = k'_f = k'_g = h'_g =u$. Let $h_f = ux$ and $h_g = uy$, $x,y\in A$. Let $v$ be the suffix of $u$ of length $R$. Since $f\sim_n g$, $vx$ and $vy$ are factors of both $f$ and $g$. Since $v$ is not right special, it follows $x=y$ and $h_f = h_g$. \finedim By a symmetric argument, the following proposition can be proved. \begin{prop} Let $f\in A^*$ and $n = L_f+1$. If $g\in A^*$ is such that $g \sim_n f$, and $h_f = h_g$, then $f = g$. \end{prop} \begin{thm} \label{propA} Let $f\in A^*$ and $n = \max\{R_f,K_f\}+1$. For any $g\in A^*$, if $g \sim_n f$, then $g = f$. \end{thm} % \emph{Proof.} Let $g\sim_n f$. By Proposition \ref{prop3}, it is sufficient to prove that $k_f=k_g$. Since $f \sim_n g$, then the factor $k_f$ of $f$ cannot be extended on the right in $g$, since otherwise $k_f$ could be also extended on the right in $f$. Hence, $k_g$ is a suffix of $k_f$. If $k_g$ is a proper suffix of $k_f$, then $k_g$ would be extendable on the right in $f$ and, by hypothesis, also in $g$, which is a contradiction. Thus, $k_f = k_g$. \finedim \begin{prop} Let $f\in A^*$ and $n = \max\{R_f,K_f\}$. There exists $g\in A^*$ such that $g \neq f$ and $g\sim_n f$. Moreover, $f \preceq_{n+1} g$ and all the factors of $g$ of length $n+1$, with the exception of one, are factors of $f$. \end{prop} % \emph{Proof.} If $f=\epsilon$, then $n=0$ and the statement is trivially satisfied by $g=a$, $a\in A$. Let us then suppose $f\neq\epsilon$. By Proposition \ref{prop1} the word $f$ has a repetition of length $n-1$, i.e. we can write \[ f = prq =p'rq', \] with $|r| = n-1$ and $|p| < |p'|$. Set $g = p'rq$. Let us prove that $f \preceq_{n+1} g$. Since $|p'| > |p|$, one has $p' = p\xi$ with $\xi\in A^+$ and then $f = p\xi r q'$. As $|\xi r| \geq n$, then a factor $u$ of $f$ of length $n+1$ is either a factor of $p\xi r = p'r$ or a factor of $\xi rq' = rq$, so that $u$ is a factor of $g$. Conversely, a factor of $g$ of length $n$ is either a factor of $p'r$ or of $rq$ and, therefore, it is a factor of $f$. This proves that $f \sim_n g$. All factors of length $n+1$ of $g$ which occur in $p'r$ or in $rq$ are also factors of $f$. The only exception is given by $xry$, where $x$ is the last letter of $p'$ and $y$ is the first letter of $q$. \finedim \begin{example} \label{esempio2} Let $A = \{a,b,c\}$ and $w = abccbabcab$. The factor $abc$ is the right special factor of $w$ of maximal length and $k_w = cab$. In this case, $R_w = 4$ and $K_w = 3$. We can write $w = prq = p'rq'$, where $r = abc$, $p = \epsilon$, $q = cbabcab$, $p' = abccb$ and $q' = ab$. Let us then consider the word $g = p'rq = abccbabccbabcab$. One easily verifies that $g\sim_4 w$, $w\preceq_5 g$ and that $babcc$ is the only factor of $g$ of length 5 which is not a factor of $w$. \end{example} \section{Boxes and reduced sets} \label{SQUATTRO} In this section we prove some structural properties of boxes. In particular it is shown that any maximal box is an unrepeated factor. Moreover, one can prove that the set of the maximal boxes in the maximal box theorem is `nearly' optimal in the sense that for any given word $w$ one can construct another word $v$ with the property that all boxes of $w$ are factors of $v$, whereas there exist at most two boxes of $v$ which are not factors of $w$. However, a simpler representation of a word is given by the so-called `reduced sets' for which a result similar to the maximal box theorem holds. \begin{prop} \label{prop5} Let $\alpha$ be a maximal box of $w$. Then $\alpha$ is an unrepeated factor of $w$. \end{prop} % \emph{Proof.} Suppose, by contradiction, that the maximal box $\alpha$ is a repeated factor of $w$. The box $\alpha$ will be a factor of a maximal repeated factor $u$ of $w$. By Proposition \ref{prop4}, there are three possibilities: 1. $u = h'_w$. In such a case it follows that $\alpha $ is a proper factor of the initial box $h_w$, which contradicts the maximality of $\alpha$ as a box. 2. $u = k'_w$. In such a case it follows that $\alpha $ is a proper factor of the terminal box $k_w$, which contradicts the maximality of $\alpha$ as a box. 3. $u$ is a bispecial factor of $w$. Since $u$ has always an internal occurrence in $w$, it can be extended in a box. The same will occur for $\alpha$, which contradicts again the maximality of $\alpha$. \finedim \begin{prop} \label{prop6} Let $w = \lambda asb \mu$, where $asb \neq k_w$ (resp. $asb \neq h_w$) is a proper maximal box of $w$ with $a,b\in A$, $s\in A^*$. If $csb$ (resp. $asc$) is a box of $w$ with $c\in A$ and $c\neq a$ (resp. $c\neq b$) having the leftmost (resp. rightmost) occurrence in $w$ given by $(\lambda' , \mu')$, then $k_w = csb\mu'$ and $\mu'\in\pref(\mu)$ (resp. $h_w = \lambda'asc$ and $\lambda'\in\suff(\lambda)$). \end{prop} % \emph{Proof.} We can write the word $w$ as \begin{equation} w = \lambda asb \mu = \lambda' csb \mu'. \label{eqBox} \end{equation} First, we show that one of the words $\mu$ and $\mu'$ is a prefix of the other one. Indeed, if it is not the case, we can write \[ \mu = ux\delta,\quad \mu' = uy\delta' \] with $x,y\in A$, $x\neq y$, $u, \delta,\delta'\in A^*$. Hence $asbux, csbuy \in F(w)$. This implies that $sbu$ is a bispecial factor, so that $asbux$ is a box properly containing $asb$. This contradicts the maximality of $asb$. Now, let us suppose that $\mu$ is a prefix of $\mu'$. By Eq.~(\ref{eqBox}), one has that $asb \mu$ is a suffix of $w$ and $sb \mu$ is repeated in $w$. This implies that $|asb \mu| \leq K_w$. Since $asb\neq k_w$, it follows that $asb$ is a proper factor of $k_w$, which contradicts the maximality of $asb$ as a box. Thus $\mu'$ is a prefix of $\mu$. By Eq.~(\ref{eqBox}), one has that $csb \mu'$ is a suffix of $w$ and $sb \mu'$ is repeated in $w$. Consequently, $csb\mu'$ is a suffix of $k_w$. If $csb\mu'$ is a proper suffix of $k_w$, then it will be repeated and this contradicts the fact that $(\lambda', \mu')$ is the leftmost occurrence of $csb$ in $w$. We conclude that $k_w = csb\mu'$. The remaining part of the proof is obtained by a symmetrical argument. \finedim The following theorem \cite{special}, whose proof we omit, shows that for any given word $w$ one can construct another word $v$ with the property that all boxes of $w$ are factors of $v$, whereas there exist at most two boxes of $v$ which are not factors of $w$. \begin{thm} \label{teor3} Let $w = \lambda asb\mu$, where $asb$ is a proper maximal box of $w$. Then, there exists a further occurrence of $s$ in $w$, i.e. $w = \xi s \eta$, such that the word $v$ defined by \begin{equation} \label{eq2} v = \left\{ \begin{array}{ll} \lambda as \eta & \mbox{if }|\lambda a| > |\xi| \\ \xi sb \mu & \mbox{if }|\lambda a| < |\xi|, \end{array} \right. \end{equation} satisfies the following conditions: \begin{enumerate} \item $\mathcal{B}_w \subseteq F(v)$, \item $1 \leq \card(\mathcal{B}_v \setminus F(w)) \leq 2$. \end{enumerate} \end{thm} \begin{example} \label{esempio3} Let $w$ be the word $w = abccbabcab$ considered in Example \ref{esempio1}. One has $h_w = abcc$, $k_w = cab$ and the maximal boxes are \[ abcc,\quad bca,\quad cab,\quad cba,\quad ccb. \] Let us underline in $w$ the occurrences of the two maximal boxes $bca$ and $ccb$: \[ w = ab\underline{ccb}abcab = abccba\underline{bca}b. \] According to Theorem \ref{teor3}, we construct the word \[ v = abccba \underline{bcb} abcab. \] One easily verifies that the maximal boxes of $v$ are $h_v = abcc$, $k_v = cab$, $ccbabcb$ and $bcbabca$. Moreover, $\mathcal{B}_w\subseteq F(v)$ and $ccbabcb$ and $bcbabca$ are the only two maximal boxes of $v$ which are not factors of $v$. \end{example} Starting from the set of maximal boxes of a given word $w$, we introduce now the so-called \emph{reduced sets} which also provide a representation of the word. These sets can be convenient since, as we shall see, the representation is simpler in the sense that any element of a reduced set is a factor of a maximal box. Let $f$ be a word and $\mathcal{B}_{f}$ be the set of its maximal boxes. We construct a new set $\mathcal{D}_{f}$ as follows. Let $s$ be a bispecial factor of $f$ and consider the set \[ \Omega_s=\{ asb\in \mathcal{B}_f \mid a,b \in A,\ as\not\in\suff(h'_f),\ sb\not\in\pref(k'_f)\}. \] If $\Omega_{s}$ is not empty, we take arbitrarily one maximal box $\alpha = asb\in\Omega_{s}$ and replace it by all boxes which are proper factors of it. Iterating these operations over all bispecial factors of $f$, we obtain a set of boxes. By deleting all elements which are not maximal, with respect to the factor order, we construct a set $\mathcal{D}_{f}$ that we call a \emph{reduced set} of $f$. We observe that, in the construction of $\mathcal{D}_{f}$, it is sufficient to replace the maximal box $\alpha\in\Omega_s$ by the longest box which is a proper prefix of $\alpha$ and the longest box which is a proper suffix of $\alpha$. Indeed, it is easily seen that any other box in $\alpha$ will not appear in a reduced set. Moreover, by the construction, any box of $f$ which is not maximal, is a factor of an element of $\mathcal{D}_{f}$. We remark that, by the arbitrary choice in each $\Omega_s$ of the maximal box to be replaced, one can obtain, in general, several distinct reduced sets. \begin{example} Let $w$ be the word $w = babacbcabaccbb$. One has $h_w = bab$, $k_w =bb$. The bispecial factors of $w$ are \[ \epsilon,\quad a,\quad b,\quad c,\quad cb,\quad abac. \] The set of maximal boxes of $w$ is \[ \mathcal{B}_w = \{ bca,\ acbc,\ ccbb,\ babacb,\ cabacc \}. \] We can construct a reduced set $\mathcal{D}_w$ in the following way. We make the following replacements: \begin{eqnarray*} bca & \rightarrow & bc,\ ca, \\ acbc & \rightarrow & acb,\ cbc, \\ babacb & \rightarrow & bab,\ acb. \end{eqnarray*} By deleting all non-maximal elements, we obtain the reduced set \[ \mathcal{D}_w = \{ bab,\ acb,\ cbc,\ ccbb,\ cabacc\}. \] \end{example} The following theorem \cite{special}, which is an analog of the maximal box theorem, holds. The proof is omitted for the sake of brevity. \begin{thm} \label{ridotti} Let $f,g \in A^*$ be two words and $\mathcal{D}_{f}$, $\mathcal{D}_{g}$ be reduced sets of $f$ and $g$, respectively. Suppose that \begin{enumerate} \item $h_f = h_g, \quad k_f = k_g$, \item $\mathcal{D}_f \subseteq F(g)$, \item $\mathcal{D}_g \subseteq F(f)$. \end{enumerate} Then $f = g$. \end{thm} \section{Superboxes} \label{SSETTE} In this section we introduce the important notion of \emph{superbox} which is strongly related to that of maximal box. An analog of the maximal box theorem is proved in the case of superboxes. Two simple algorithms are given, the first allows us to determine the superboxes of any word $w$, the second permits to reconstruct the word starting from $h_w$, $k_w$ and the set of all superboxes. \begin{prop} \label{prop10} Let $f = asb$ be a box of the word $w$ with $a,b\in A$, $s\in A^{*}$ such that $as$ and $sb$ are unrepeated. Then $f$ is a maximal box. \end{prop} % \emph{Proof.} Suppose that $asb$ is not maximal. Then, there exists a box $\alpha$ such that $\alpha=\lambda asb\mu$, where $\lambda,\mu\in A^*$ and $\lambda\mu \neq \epsilon$. It follows that either $as$ or $sb$ is an internal factor of $\alpha$ and then, by Lemma \ref{lemma1}, a repeated factor of $w$, which is a contradiction. \finedim We shall set \[ \mathcal{M}_w = \{ asb \in F(w) \mid a,b\in A,\ s \mbox{ repeated and } as,sb\mbox{ unrepeated.}\} \] The elements of $\mathcal{M}_w$ will be called \emph{superboxes}. The reason of this name is due to the fact that, as we shall prove by Proposition \ref{propsuper}, any element of $\mathcal{B}_w \setminus \{h_{w}, k_{w} \}$ is a factor of an element of $\mathcal{M}_w$. Let us recall (cf. \cite{theorycodes}) that a subset $X$ of $A^*$ is called a \emph{factor code} if no word of $X$ is a proper factor of another word of $X$. \begin{prop} \label{factorcode} Let $w$ be a word. The set $\mathcal{M}_w$ is a factor code. Moreover, no element of $\mathcal{M}_w$ can be a factor of $h_w$ or of $k_w$. \end{prop} % \emph{Proof.} Suppose by contradiction that $asb, ctd\in\mathcal{M}_w$, with $a,b,c,d\in A$, $s,t\in A^*$, and that $asb$ is a proper factor of $ctd$. This implies that either $as$ or $sb$ is a factor of $t$, which is absurd since $t$ is a repeated factor of $w$. Suppose now that $asb$ is a factor of $h_w$ (resp. $k_w$). Then $as$ (resp. $sb$) is a factor of $h'_w$ (resp. $k'_w$) and then it is a repeated factor, which is a contradiction. \finedim \begin{prop} \label{propprima} Let $f = asb\in \mathcal{M}_w$ with $a,b\in A$ and $s\in A^*$. If $s \neq k'_w$ and $s \neq h'_w$, then $f$ is a proper maximal box. \end{prop} % \emph{Proof.} Since $s$ is a repeated factor of $w$, there will be at least another occurrence of $s$ in $w$. Let us prove that we can always reduce ourselves to consider only the case when this occurrence is internal. Let us suppose that $s$ is a suffix of $w$. Then there exists a letter $c$ such that $cs$ is a suffix of $w$, and $c \neq a$, since $as$ is unrepeated. If $|cs|K_w$, then $|s| \geq K_w$. This implies that $s$ is unrepeated, which is a contradiction. Finally, if $|cs| = K_w$ one has $s = k'_w$, which contradicts the hypothesis made. The case when $s$ is a prefix is dealt with a symmetric argument. Let us consider then the case that the further occurrence of $s$ is internal. In such a case, there exist two letters $c,d\in A$, for which $csd\in F(w)$. One has $c\neq a$ and $d \neq b$, because $as$ and $sb$ are unrepeated. This implies that $s$ is a bispecial factor and that $f = asb$ is a proper box. By Proposition \ref{prop10}, the result follows. \finedim \begin{prop} Let $asb$ be a proper maximal box of the word $w$, with $a,b\in A$ and $s\in A^*$. If $sb$ (resp. $as$) is neither a prefix (resp. suffix) of $k'_w$ nor of $h'_w$, then $sb$ (resp. $as$) is unrepeated. \end{prop} % \emph{Proof.} Suppose that $sb$ is a repeated factor of $w$. If $sb$ is a prefix of $w$, then $sb$ has to be a prefix of $h'_w$, which has been excluded. Thus there is a letter $c$ such that $csb$ is a factor of $w$ and $c \neq a$, since $asb$ is unrepeated by Proposition \ref{prop5}. By Proposition \ref{prop6}, one derives that $csb$ is a prefix of $k_w$ and then $sb$ is a prefix of $k'_w$, which has been excluded. Thus, $sb$ is unrepeated. The remaining part of the proof is carried out in a symmetrical way. \finedim \begin{prop} \label{propsuper} Any maximal box $\alpha$ of a word $w$, such that $\alpha\neq h_w$ and $\alpha\neq k_w$ is a factor of a superbox. \end{prop} % \emph{Proof.} Let $\alpha = asb$ be a proper maximal box of $w$ such that $\alpha\neq h_w$ and $\alpha\neq k_w$. We consider the set of all factors of $w$ of the kind $f = xry$ where $x,y\in A$, $r$ is a repeated factor of $w$ and $\alpha$ is a factor of $f$. Let us take in this set a maximal element, with respect to factor ordering, say $\beta = ctd$, with $c,d\in A$, $t\in A^*$. Let us prove that $\beta\in \mathcal{M}_w$. Let us first suppose that $td$ is repeated. If $\beta$ is right extendable, then one contradicts the maximality of $\beta$. If $\beta$ is not right extendable, since $td$ is repeated, then $\alpha \preceq \beta = k_w$. Since $\alpha\neq k_w$, one contradicts the maximality of $\alpha$ as a box. This proves that $td$ is unrepeated. In a symmetric way, one shows that $ct$ is unrepeated. \finedim \begin{prop} \label{propseconda} The maximal boxes $\alpha \in \mathcal{B}_w \setminus \{h_w, k_w\}$ are either superboxes or prefixes or suffixes of elements of $\mathcal{M}_w \cap A\{h'_w, k'_w\}A$. \end{prop} % \emph{Proof.} Let $\alpha \in \mathcal{B}_w \setminus \{h_w, k_w\}$. By Proposition \ref{propsuper}, one has that $\alpha$ is a factor of a superbox $\beta$. Hence either $\alpha = \beta$ or $\alpha$ is a proper factor of $\beta$. In this latter case, $\beta$ is not a maximal box. By Proposition \ref{propprima}, it follows that $\beta\in A\{h'_w, k'_w\}A$. Since $\alpha$ is a maximal box, $\alpha$ cannot be a factor of $h'_w$ or of $k'_w$ and then, necessarily, it is a prefix or a suffix of $\beta$. \finedim \begin{prop} Let $f,g \in A^*$ be two words such that \begin{enumerate} \item $h_f \in\pref(g), \: k_f \in\suff(g), \: h_g \in\pref(f), \: k_g \in\suff(f)$, \item $\mathcal{M}_f \subseteq F(g)$, \item $\mathcal{M}_g \subseteq F(f)$. \end{enumerate} Then $f = g$. \end{prop} % \emph{Proof.} By Proposition \ref{propsuper}, any element of $\mathcal{B}_f$ is a factor of an element of $\mathcal{M}_f\cup\{h_f,k_f\}$ and any element of $\mathcal{B}_g$ is a factor of an element of $\mathcal{M}_g\cup\{h_g,k_g\}$. Hence, $\mathcal{B}_f\subseteq F(g)$ and $\mathcal{B}_g\subseteq F(f)$. Thus, by the maximal box theorem, it is sufficient to prove that $h_f = h_g$ and $k_f = k_g$. Let us prove that $h_f = h_g$. By (i), we can write $f$ as $f = h_f\xi = h_g\xi'$, $\xi,\xi'\in A^*$ and $g = h_g\lambda = h_f\lambda'$, $\lambda, \lambda'\in A^*$. Let us suppose that $|h_f|<|h_g|$. This implies that $h_f$ is a prefix of $h'_g$ and then it is repeated in $g$. We consider a further occurrence of $h_f$ in $g$ and a repeated factor $\alpha$ of $g$ of maximal length containing as a factor such an occurrence of $h_f$. We can write $g$ as $g = \delta \alpha \mu$ with $\delta, \mu\in A^*$. If $\delta$ and $\mu$ are non-empty, then there exist letters $x$ and $y$ such that $x\alpha y$ is a factor of $g$ and $x\alpha$, $\alpha y$ are unrepeated. Thus, $x\alpha y \in \mathcal{M}_g$ and then $x\alpha y$ is a factor of $f$. One derives that in $f$ there is a repeated occurrence of $h_f$, which is a contradiction. Now, suppose $\delta = \epsilon$. Since $\alpha$ is repeated, $\alpha$ is a proper prefix of $h_g$ and, therefore, $h_f$ has two occurrences in $h_g$. Since $h_g\in F(f)$, this is a contradiction. Finally, if $\mu=\epsilon$, then $\alpha$ is a suffix of $k'_g$ which, by (i), is a proper suffix of $f$. Thus $\alpha$ has a non-initial occurrence in $f$. Consequently $h_f$ is repeated, which is a contradiction. Thus, $|h_f|\geq |h_g|$. Symmetrically, one can prove that $|h_g|\geq |h_f|$ and then $h_f = h_g$. In a symmetric way, one proves that $k_f = k_g$, which concludes the proof. \finedim Let $\alpha,\beta\in A^*$. We denote by $\alpha \wedge \beta$ the maximal overlap of $\alpha$ with $\beta$, i.e. the suffix of maximal length of $\alpha$ which is a prefix of $\beta$. Then $\alpha$ and $\beta$ can be written as $\alpha = \lambda (\alpha\wedge \beta)$, $\beta = (\alpha\wedge \beta)\mu$, $\lambda,\mu\in A^*$. We shall denote by $\alpha\vee \beta$ the word \[ \alpha\vee \beta = \lambda (\alpha\wedge \beta) \mu = \alpha\mu = \lambda \beta. \] \begin{lemma} \label{incolla} Let $u$ and $v$ be two factors of a word $w\in A^*$. If $t$ is an unrepeated factor of $w$ such that $t\in\suff(u)\cap\pref(v)$, then $t=u\wedge v$ and $u\vee v\in F(w)$. \end{lemma} % \emph{Proof.} One has $u=\xi t$ and $v=t\eta$, where $\xi,\eta\in A^*$. Since $|t|\leq |u\wedge v|$, $t$ is both a prefix and a suffix of $u\wedge v$. But $t$ is unrepeated and, therefore, necessarily $t=u\wedge v$. Moreover, the only occurrence of $t$ in $w$ has to be preceded by $\xi$ and followed by $\eta$, so that $u\vee v=\xi t\eta\in F(w)$. \finedim If $t,u,v\in F(w)$ and both $\suff(t)\cap\pref(u)$ and $\suff(u)\cap\pref(v)$ contain elements which are unrepeated factors of $w$, then one has $(t\vee u)\vee v =t\vee(u\vee v)$. Indeed, by an iterated application of Lemma \ref{incolla}, one has that $(t\vee u)\vee v$ and $t\vee(u\vee v)$ are both factors of $w$ beginning by $t$ and ending by $v$. They must coincide, since $t$ and $v$ are unrepeated in $w$. More generally, if $\alpha_0,\alpha_1,\ldots, \alpha_n\in F(w)$ and, for any $i=0,1,\ldots,n-1$, $\suff(\alpha_i)\cap\pref(\alpha_{i+1})$ contains an element which is an unrepeated factor of $w$, then one can consider the word $\alpha_0\vee\alpha_1\vee\cdots\vee\alpha_n$, in which the parentheses are omitted since its value is independent from the order with which the operations are performed. Let us now introduce a sequence $\Gamma_w=(\alpha_0,\alpha_1,\ldots, \alpha_n)$ of elements of $\mathcal{M}_w\cup\{h_w,k_w\}$ giving a covering of $w$. We shall call $\Gamma_w$ also the \emph{covering sequence} of $w$. In the first step, we set $\alpha_0=h_w$. Now suppose that we have determined the element $\alpha_i\in\mathcal{M}_w\cup \{h_w\}$ ($i\geq 0$). Let $u$ be the shortest suffix of $\alpha_i$ which is unrepeated in $w$ and write $u=at$ with $a\in A$ and $t$ repeated in $w$. One can uniquely write $w=\lambda at\mu$, with $\lambda,\mu\in A^*$. If $t\mu$ is a repeated factor of $w$, then, since $at\mu$ is unrepeated in $w$, one has $at\mu=k_w$. In this case, we set $\alpha_{i+1}=k_w$ and this is the last element of the sequence. Otherwise, we set $\alpha_{i+1}=ar$, where $r$ is the shortest prefix of $t\mu$ which is unrepeated in $w$. In this latter case, one has $r=sb$, with $b\in A$ and $s$ is a repeated factor of $w$, while $as$ is unrepeated in $w$, since it contains the prefix $u=at$. Thus, $\alpha_{i+1}\in\mathcal{M}_w$. In other words, each element of the sequence $\Gamma_w$, excepted the first one, is obtained by taking the shortest suffix of the previous one which is unrepeated in $w$ and extending it in $w$ until one finds either a superbox or $k_w$. \begin{example} \label{esempio6} Let $w$ be the word $abccbabcab$. The previous procedure generates the covering sequence of $w$ \[ abcc,\quad ccb,\quad cba,\quad babca,\quad cab. \] One has $h_w = abcc$ and $k_w = cab$. \end{example} \begin{prop} \label{propcover} Let $w$ be a word and $\Gamma_w=(\alpha_0,\alpha_1,\ldots, \alpha_n)$ be the covering sequence of $w$. Then one has \begin{equation} w=\alpha_0\vee\alpha_1\vee\cdots\vee\alpha_n \label{eq:cover} \end{equation} and \begin{equation} \mathcal{M}_w=\{\alpha_1,\alpha_2,\ldots, \alpha_{n-1}\}. \label{eq:cover2} \end{equation} \end{prop} % \emph{Proof.} By the definition of $\Gamma_w$, for any $i=0,1,\ldots,n-1$, there is an unrepeated factor $t$ of $w$ such that $t\in\suff(\alpha_i)\cap\pref(\alpha_{i+1})$. Thus, by an iterated application of Lemma \ref{incolla}, one gets that the right hand side of Eq.~(\ref{eq:cover}) is a factor of $w$. Since it contains both $h_w$ and $k_w$ it must be necessarily equal to the entire $w$, so that Eq.~(\ref{eq:cover}) is proved. Consequently, any factor of $w$ either is a factor of an element of $\Gamma_w$ or contains a word $\alpha_i\wedge\alpha_{i+1}$ as an internal factor, for some $i=0,1,\ldots,n-1$. Since the words $\alpha_i\wedge\alpha_{i+1}$ are unrepeated, they cannot occur as internal factors of a superbox and, therefore, any superbox is necessarily a factor of an element of $\Gamma_w$. In view of Proposition \ref{factorcode}, one easily derives Eq.~(\ref{eq:cover2}). \finedim In the sequel, we shall denote $\mathcal{M}_w \cup \{h_w,\ k_w\}$ by $\mathcal{M}'_w$. Proposition \ref {propcover} ensures that the elements of $\mathcal{M}'_w$ are exactly the elements of $\Gamma_w$ and, therefore, $\mathcal{M}'_w$ is a covering of $w$. Let us observe that, in general, the set of maximal boxes $\mathcal{B}_w$ of the word $w$ is not a covering. For instance, in the case of the word $w=abcdebcd$, one has $\mathcal{B}_w = \{ ab, de, ebcd\}$ which is not a covering of $w$. Next proposition shows that, once we know the initial box $h_w$ of a word $w$ and the set $\mathcal{M}'_w$, we can effectively order the elements of $\mathcal{M}'_w$ to obtain $\Gamma_w$. \begin{prop} \label{propDelta} Let $w$ be a word and $\Gamma_w=(\alpha_0,\alpha_1,\ldots, \alpha_n)$ be the covering sequence of $w$. Set $\delta_i=|\alpha_i\wedge\alpha_{i+1}|$, $0\leq i\leq n-1$. Then $\alpha_{i+1}$ is the only element $\beta\in\mathcal{M}'_w\setminus\{\alpha_i\}$ such that $|\alpha_i\wedge\beta|\geq \delta_i$. \end{prop} % \emph{Proof.} Suppose $\beta\in\mathcal{M}'_w\setminus\{\alpha_i\}$ and $|\alpha_i\wedge\beta|\geq \delta_i$. Let $u$ be the shortest suffix of $\alpha_i$ which is unrepeated in $w$. By the definition of $\Gamma_w$, $u$ is a prefix of $\alpha_{i+1}$, so that, by Lemma \ref{incolla}, $|u|=|\alpha_i\wedge\alpha_{i+1}|=\delta_i\leq|\alpha_i\wedge\beta|$. One derives that $u$ occurs in $\beta$. But, by the way the procedure for the construction of the covering sequence is carried out, the only elements of $\Gamma_w$ in which $u$ occurs are $\alpha_i$ and $\alpha_{i+1}$, so that $\beta=\alpha_{i+1}$. \finedim To reconstruct a word $w$, knowing $h_w$ and $\mathcal{M}'_w$, first one has to arrange the elements of $\mathcal{M}'_w$ to obtain $\Gamma_w$ and then use Eq.~(\ref{eq:cover}). The first operation is realized by observing that the first element of $\Gamma_w$ is $h_w$ and that each non-terminal element $\alpha_i$ of $\Gamma_w$ is followed by the element $\beta\in\mathcal{M}'_w\setminus\{\alpha_i\}$ such that the overlap of $\alpha_i$ with $\beta$ has maximal length. An unrepeated factor of $w$ is called \emph{minimal} if any of its proper factors is repeated. Let us denote by $\mathcal{U}_w$ the set of the minimal unrepeated factors of $w$. \begin{prop} Let $w$ be a word and $\Gamma_w=(\alpha_0,\alpha_1,\ldots, \alpha_n)$ be the covering sequence of $w$. Then one has \[ \mathcal{U}_w = \{\alpha_0\wedge\alpha_1, \alpha_1\wedge\alpha_2,\ldots, \alpha_{n-1}\wedge\alpha_n\}. \] \end{prop} % \emph{Proof.} By construction, the maximal overlap of an element $\alpha_i$ with the consecutive $\alpha_{i+1}$, $0\leq i\leq n-1$, is a minimal unrepeated factor of $w$. Conversely, let $u\in \mathcal{U}_w$. We can write uniquely $w = \lambda u \mu$, with $\lambda, \mu \in A^*$. Since $u$ is minimal unrepeated, one has $u = rb$, with $b \in A$ and $r$ is a repeated factor of $w$. Thus $w = \lambda rb \mu$. If $\lambda r$ is repeated, since $\lambda rb$ is unrepeated, then $\lambda rb = h_w$. Otherwise, consider the shortest unrepeated suffix of $\lambda r$; we can write it as $as$, with $a\in A$ and $s$ is a repeated factor. Thus, in this case, since $sb$ is unrepeated, $asb\in \mathcal{M}_w$. Hence, in any case, $u$ can be extended on the left in $w$ in an element of $\Gamma_w$, say $\alpha_i$, with $0\leq i\leq n-1$. Moreover, $u$ is the shortest suffix of $\alpha_i$ unrepeated in $w$, so that it is also a prefix of $\alpha_{i+1}$. By Lemma \ref{incolla}, one has $u=\alpha_i\wedge\alpha_{i+1}$. \finedim The following `uniqueness' result was proved in \cite{special}: \begin{prop} Let $w\in A^*$. Then $w$ is the unique word of minimal length which begins by $h_w$, ends by $k_w$ and contains the elements of $\mathcal{M}_w$ as factors. \end{prop} In conclusion of this section, we mention that some general theorems relating Nerode's equivalence of the language of the factors of a word and the theory presented in the previous sections are proved in \cite{special}. \section{A box theorem for languages} \label{sec.languages} By language on the alphabet $A$ we mean any non-empty subset $L$ of $A^*$. A language is called \emph{factorial} if $L=F(L)$. The notions of extendable factor, special factor and box can be naturally extended to languages, as follows. A factor $u$ of a language $L$ is said to be \emph{right} (resp. \emph{left}) \emph{extendable} in $L$ if there exists a letter $a\in A$ such that $ua\in F(L)$ (resp. $au\in F(L)$). We shall denote by $U_L$ the set of all factors of $L$ which cannot be extended on the left in $L$, i.e. \[ U_L=\{u\in F(L)\mid Au\cap F(L)=\emptyset\}. \] In a symmetrical way, $V_L$ will denote the set of all factors of $L$ which cannot be extended on the right in $L$, i.e. \[ V_L=\{u\in F(L)\mid uA\cap F(L)=\emptyset\}. \] We shall denote by $U^0_L$ (resp. $V^0_L$) the set of the elements of $U_L$ (resp. $V_L$) which are minimal with respect to the prefix (resp. suffix) order. One has: \[ U^0_L=U_L\setminus U_LA^+,\quad V^0_L=V_L\setminus A^+V_L. \] Let $L$ be a language over the alphabet $A$. A word $s$ of $A^*$ is called a \emph{right} (resp. \emph{left}) \emph{special factor} of $L$ if there exist $x,y\in A$, $x\neq y$, such that $sx, sy \in F(L)$ (resp. $xs, ys \in F(L)$). A word of $A^*$ which is a right and left special factor of $L$ is called a \emph{bispecial factor} of $L$. We introduce the set $B_L$ of the proper boxes of $L$. A \emph{proper box} $\alpha$ of $L$ is a factor of $L$ of the kind $\alpha=asb$ with $a,b\in A$ and $s$ a bispecial factor of $L$. Any element of $U^0_L$ (resp. $V^0_L$) is called an \emph{initial} (resp. \emph{terminal}) \emph{box}. By \emph{box}, without specification, we mean indifferently an initial, a terminal or a proper box. Let $L,M$ be two languages over the alphabet $A$ such that $F(L)\neq F(M)$. A \emph{separating factor} of $L$ and $M$ is any word in the symmetric difference $(F(L) \setminus F(M))\cup (F(M) \setminus F(L))$. A \emph{minimal separating factor} of $L$ and $M$ is a separating factor of minimal length. The following lemma, whose proof is in \cite{2D}, is the key result which allows us to prove a box theorem for languages. % \begin{lemma}\label{lem.2} Let $L,M\subseteq A^*$ be two languages such that $F(L)\neq F(M)$ and let $u$ be a minimal separating factor of $L$ and $M$. Set $p=\max\{2, |u|\}$. If the following conditions are satisfied \begin{itemize} \item[1)] $U^0_L\cap A^{p-1}=U^0_M\cap A^{p-1},\quad V^0_L\cap A^{p-1}=V^0_M\cap A^{p-1}$ \item[2)] $B_L\cap A^{p}\subseteq F(M),\quad B_M\cap A^{p}\subseteq F(L)$, \end{itemize} then $\mathrm{Card}(\mathrm{alph}(L)), \mathrm{Card}(\mathrm{alph}(M))\leq 1$. \end{lemma} % % \begin{thm} \label{thm.maxbox} Let $L$ and $M$ be languages on the alphabet $A$. If the following conditions are satisfied: \begin{itemize} \item[1)] $U^0_L=U^0_M,\quad V^0_L=V^0_M$ \item[2)] $B_L\subseteq F(M),\quad B_M\subseteq F(L)$, \end{itemize} then either $F(L)=a^*$, $F(M)=b^*$, with $a,b\in A$ and $a\neq b$, or $F(L)=F(M)$. \end{thm} % \emph{Proof.} We shall prove that if $F(L)\neq F(M)$, then $F(L)=a^*$, $F(M)=b^*$, with $a,b\in A$ and $a\neq b$. By Lemma \ref{lem.2}, one has $\mathrm{Card}(\mathrm{alph}(L)), \mathrm{Card}(\mathrm{alph}(M))\leq 1$. In such a case, either $V^0_L\neq\emptyset$ and $F(L)=F(V^0_L)$ or $V^0_L=\emptyset$ and $L$ is an infinite language; similarly, one has that either $V^0_M\neq\emptyset$ and $F(M)=F(V^0_M)$ or $V^0_M=\emptyset$ and $M$ is an infinite language. Thus, if $V^0_L=V^0_M\neq\emptyset$, one would have \[ F(L)=F(V^0_L)=F(V^0_M)=F(M), \] which is a contradiction. The only remaining possibility is that $V^0_L=V^0_M=\emptyset$ and $L\subseteq a^*$ and $M\subseteq b^*$ are infinite languages, with $a\neq b$. \finedim Let us observe that the preceeding theorem is, in fact, a box theorem for factorial languages (with the only exception of a trivial case). However, by using boardmarkers for the words of the language $L$, a box theorem for languages can be easily derived. More precisely, let us consider a new alphabet $A_0=A\cup \{\#\}$, where $\#\not\in A$. For any language $L\subseteq A^*$, we introduce the language \[ \hat{L}= \#L\#. \] The following theorem holds \cite{2D}. \begin{thm} \label{thm.dollar} Let $L$ and $M$ be languages on the alphabet $A$ such that \[ \mathcal{B}_{\hat{L}} \subseteq F(\hat{M}),\quad \mathcal{B}_{\hat{M}} \subseteq F(\hat{L}). \] Then $L=M$. \end{thm} An infinite word $f$ (from left to right) on the alphabet $A$ is any map $f:\mathbb{N}_+\rightarrow A$. We shall set for any $i\geq 1$, $f_i=f(i)$ and write \[ f=f_1f_2\cdots f_n\cdots . \] A word $u\in A^*$ is a \emph{factor} of $f$ if $u=\epsilon$ or there exist integers $i,j$ such that $1\leq i\leq j$ and $u=f_i\cdots f_j$. The set of all factors of $f$ is denoted by $F(f)$. A factor $u$ of an infinite word $f$ is called respectively \emph{right special}, \emph{left special}, \emph{bispecial} if it is a right special, left special, bispecial factor of $F(f)$. For an infinite word $f$ we shall write $B_f$, $U^0_f$ and $V^0_f$ instead of $B_{F(f)}$, $U^0_{F(f)}$ and $V^0_{F(f)}$. An infinite word $f$ is \emph{periodic} of period $p$ if for any $i\geq 1$ one has $f_i=f_{i+p}$. As an application of Theorem \ref{thm.maxbox}, we shall give a new proof of the `uniqueness theorem' for periodic functions of Fine and Wilf \cite{fine}, in the discrete case. We recall that this theorem can be stated as follows. % \begin{thm} Let $f$ and $g$ be two infinite periodic words of periods $p$ and $q$, respectively. Let $d=\gcd(p,q)$. If \[ f_1 f_2\cdots f_{p+q-d} = g_1 g_2\cdots g_{p+q-d}, \] then $f=g$. \end{thm} % \emph{Proof.} If $p=q$ the result is trivial. Thus, we can always suppose $p1$. For any $r=1,2,\ldots,d$, consider the infinite words \[ f_rf_{r+d}f_{r+2d}\cdots f_{r+nd}\cdots , \] \[ g_rg_{r+d}g_{r+2d}\cdots g_{r+nd}\cdots . \] They have respectively periods $\frac{p}{d}$ and $\frac{q}{d}$. Moreover they have the same initial segment of length $\frac{p+q}{d}-1$ so that, by the preceding result, they are equal. It follows that $f=g$. \finedim In conclusion, we mention that the notion of `special factor' can be extended in a natural way to the case of sets of bidimensional words (\emph{pictures}), taking into account \emph{right}, \emph{left}, \emph{up}, and \emph{down extensions} of subpictures. In this way, one can generalize in a suitable way the notion of box. A box theorem for picture languages, extending Theorem \ref{thm.dollar}, is proved in \cite{2D}. \begin{thebibliography}{99} \bibitem{BMR} M.-P. B\'eal, F. Mignosi and A. Restivo, Minimal forbidden words and symbolic dynamics, Proc. STACS '96, Lecture Notes in Computer Science, Springer-Verlag, vol. 1046, 1996, pp. 555--566. \bibitem{theorycodes} J. Berstel and D. Perrin, \emph{Theory of codes}, Academic Press, New York, 1985. \bibitem{special} A. Carpi and A. de Luca, Words and Special Factors, Preprint 98/33, Dipartimento di Matematica dell'Universit\`a di Roma `La Sapienza', 1998. \bibitem{2D} A. Carpi and A. de Luca, Repetitions and Boxes in Words and Pictures, Preprint 98/44, Dipartimento di Matematica dell'Universit\`a di Roma `La Sapienza', 1998. \bibitem{CASSA} J. Cassaigne, Complexit\'e et facteurs speciaux, \emph{Bull. Belg. Math. Soc.} \textbf{4} (1997) 67--88. \bibitem{adl98} A. de Luca, On the Combinatorics of Finite Words, \emph{Theoretical Computer Science}, Special Issue for the workshop `Words', to appear. \bibitem{DM} A. de Luca and F. Mignosi, Some Combinatorial properties of Sturmian words, \emph{Theoretical Computer Science} \textbf{136} (1994) 361--385. \bibitem{DELIMI} A. de Luca and L. Mione, On bispecial Factors of the Thue-Morse word, \emph{Information Processing Letters} \textbf{49} (1994) 361--385. \bibitem{DELVA} A. de Luca and S. Varricchio, On the factors of the Thue-Morse word on three symbols, \emph{Information Processing Letters} \textbf{27} (1988) 281--285. \bibitem{DELV} A. de Luca and S. Varricchio, Some combinatorial problems of the Thue-Morse sequence and a problem in semigroups, \emph{Theoretical Computer Science} \textbf{63} (1989) 333--348. \bibitem{fine} N. J. Fine and H. S. Wilf, Uniqueness Theorem for Periodic Functions, \emph{Proc. Amer. Math. Soc.}, \textbf{16} (1965) 109--114. \end{thebibliography} \bigskip\bigskip\bigskip\noindent \begin{tabular}{lcl} Arturo Carpi &~& Aldo de Luca \\ Istituto di Cibernetica &~& Dipartimento di Matematica\\ CNR &~& Universit\`a di Roma `La Sapienza' \\ via Toiano, 6 &~& piazzale Aldo Moro, 2 \\ 80072 Arco Felice (NA), Italy &~& 00185 Roma, Italy \\ \small{\texttt{arturo@arturo.cib.na.cnr.it}} &~& \small{\texttt{deluca@mercurio.mat.uniroma1.it}} \end{tabular} \end{document}