Detecting morphic images of a word: on the rank of a pattern

Jean Néraud
LIFAR, Université de Rouen, Place Émile Blondel, 76821 Mont-Saint-Aignan, France

Abstract: We study the general problem that consists in detecting the morphic images of a given word R, namely the pattern, in an arbitrary text w. We introduce the concept of rank of a pattern, which measures the complexity of its recognition in terms of periodicity. This notion leads to improve the general ``naive'' algorithm. A special class of equations in words is also concerned.

More precisely, given a word w, consider the following classical equivalence E[p]:
We have i E[p] j iff the factor of w with length p and position i is equal to the factor of length p and position j.
Clearly, the word w itself is completely determined by equivalence E[1]. Our algorithm consists in constructing a family T of binary relations that generate the equivalence E[1]. These binary relations are of type t(i,j)[k]= { (i,j), (i+1,j+1), ... (i+k-1,j+k-1)}. The rank of T is defined by the minimal cardinality of such a family T.

Example
Consider the word R= XYZXYZXYXZYXXZ upon the alphabet {X,Y,Z }. E[1] has excatly the three following classes: {1,4,7,9,12}, {2,5,8,11}, {3,6,10,13}.
We have T = { t(1,4)[5], t(8,11)[5], t(7,9)[1], t(7,10)[1] }

Page d'accueil de l'atelier
Présentation de l'atelier
Description des activités
Bibliographie