Séminaire Lotharingien de Combinatoire, B42l (1999), 24 pp.
Arturo Carpi, Aldo de Luca
Words and Repeated Factors
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 box.
The
initial (resp. terminal) box of w is the shortest prefix (resp. suffix) of w
which is an unrepeated factor. A factor u of w is a proper box if there
are letters a, a', b, b', with a' different from a and b' different
from b, such that u = asb and a's, sb' are factors of w. A box is
called maximal if it is not a proper factor of another box. The main result of
the paper is the following theorem (maximal box theorem): 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 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.
Received: December 16, 1998; Accepted: March 24, 1999.
The following versions are available: