Mot quasi-périodique

En combinatoire, et plus particulièrement en combinatoire des mots, un mot quasi-périodique est un mot fini ou infini qui peut être construit par concaténations ou superpositions d'un de ses facteurs propres. La notion de mot quasi-périodique généralise celle de mot périodique.

Les régularités dans les chaînes de caractères sont étudiées dans divers domaines scientifiques, comme la combinatoire, le codage et la compression, la théorie des automates, la biologie moléculaire, les langages formels, la théorie des systèmes. Une structure typique de régularité est la répétition dans une mot ; la période ${\displaystyle u}$ d'un mot ${\displaystyle x}$ rend compte de la nature répétitive d'un mot ${\displaystyle x}$, puisque ${\displaystyle x}$ est construit par la concaténation de copies du mot ${\displaystyle u}$. On généralise cette notion en permettant de chevauchement entre des occurrences du segment répété. Une quasi-période d'un mot ${\displaystyle x}$ est une facteur propre ${\displaystyle u}$ de ${\displaystyle x}$ tel que ${\displaystyle x}$ peut être construit à partir d'instances éventuellement chevauchantes de ${\displaystyle u}$.

Un mot est ${\displaystyle x=a_{1}\cdots a_{n}}$ est périodique s'il existe un entier ${\displaystyle p}$, avec ${\displaystyle 0<p<n}$ tel que ${\displaystyle a_{i}=a_{i+p}}$ pour ${\displaystyle 1\leq i<i+p\leq n}$ ; le plus petit entier ${\displaystyle p}$ avec cette propriété est la période minimale, ou la période tout court ; un facteur de longueur ${\displaystyle p}$ est un motif périodique, appelé aussi lui-même une période du mot. Par exemple, le mot ${\displaystyle x=abaabaab=aba.aba.ab}$ est périodique de période 3.

Si ${\displaystyle s=uv}$ et ${\displaystyle t=vw}$ sont deux mots, alors le mot ${\displaystyle uvw(=sw=ut)}$ est une superposition de ${\displaystyle s}$ et ${\displaystyle t}$. On est intéressé par des superpositions d'un même facteur dans un mot : si ${\displaystyle s=t}$, le mot${\displaystyle uvw=sw=ut}$ peut être vu comme le produit du préfixe ${\displaystyle u}$ de ${\displaystyle s}$ par le mot ${\displaystyle s}$ lui-même, ou comme produit de ${\displaystyle s}$ par le suffixe ${\displaystyle w}$ de ${\displaystyle s}$. Ainsi pour ${\displaystyle s=aba}$, le mot ${\displaystyle ababa}$ s'écrit ${\displaystyle ab\cdot aba=aba{\cdot }ba}$.

Étant donné un mot ${\displaystyle x}$, un facteur ${\displaystyle w}$ de ${\displaystyle x}$ tel que ${\displaystyle x}$ peut être construit par concaténation et superpositions de ${\displaystyle w}$ fournit une couverture alignée de ${\displaystyle x}$^[1]. Le mot ${\displaystyle w}$ est lui-même appelé un mot couvrant, ou germe (seed en anglais), le mot couvrant le plus court est appelé la quasi-période, et le mot ${\displaystyle x}$ est quasi-périodique.

Dans cette définition, le mot ${\displaystyle w}$ est à la fois préfixe et suffixe de ${\displaystyle x}$. Par exemple, le mot ${\displaystyle x=abaabababaaba}$ est quasi-périodique de mot couvrant ${\displaystyle w=aba}$ : ${\displaystyle x=aba.ab.ab.aba.aba}$. Dans cette écriture, on factorise le mot en préfixes du mot couvrant. La factorisation commence et finit par le mot couvrant tout entier : ainsi la factorisation est « alignée » sur les extrémités du mot, ce qui justifie la terminologie. Un mot est super-primitif s'il ne possède pas de couverture alignée.

Pour le mot ${\displaystyle w=aabaa}$, les plus petits mots quasi-périodiques de période ${\displaystyle w}$ sont : ${\displaystyle aabaabaa}$,
${\displaystyle aabaaabaa}$,
${\displaystyle aabaabaabaa}$,
${\displaystyle aabaabaaabaa}$,
${\displaystyle aabaababaabaa}$. Le mot ${\displaystyle aabaabaaba}$ ne figure pas dans cette liste parce qu'il ne finit pas par ${\displaystyle w}$.

Un algorithme linéaire du calcul du mot couvrant le plus court est donné par Apostolico, Farach et Iliopoulos^[2]. Un algorithme de calcul en ligne est de Dany Breslauer^[3]. Apostolico et Ehrenfeucht^[4] considèrent le calcul du plus long mot ouvrant ; ils décrivent un algorithme en ${\displaystyle O(n\log ^{2}n)}$ pour calculer tous les mots couvrants maximaux d'un mot de longueur ${\displaystyle n}$.

La définition ci-dessus fait qu'un mot qui est périodique n'a pas toujours une couverture alignée de même période. Par exemple, le mot ${\displaystyle x=abaabaab}$ est périodique de période 3 et est quasi-périodique de germe ${\displaystyle abaab}$ ; de même ${\displaystyle x=abcabcabca}$ est quasi-périodique de période ${\displaystyle abca}$ : ${\displaystyle x=abc.abc.abca}$, mais a période minimale 3.

C'est pourquoi on considère une notion plus générale : une couverture de ${\displaystyle x}$ est une couverture alignée d'un sur-mot (superstring) ${\displaystyle y}$ de ${\displaystyle x}$, c'est-à-dire d'un mot ${\displaystyle y}$ qui a ${\displaystyle x}$ en facteur. Par exemple, ${\displaystyle w=abca}$ est un germe de ${\displaystyle x=abc.abca.abc}$. Le mot ${\displaystyle w}$ est un germe (seed) de ${\displaystyle x}$. Un germe de longueur minimale n'est pas forcément unique ; ainsi ${\displaystyle abababa}$ a les deux germes ${\displaystyle ab}$ et ${\displaystyle ba}$. Un mot est quasi-périodique s'il possède une couverture dont le germe est un facteur strict du mot^[4].

Dans cette notion plus générale, un mot périodique est aussi quasi-périodique de cette longueur.

Pour ${\displaystyle x=ababaababa}$, les mots ${\displaystyle aba}$ et ${\displaystyle ababa}$ fournissent des couvertures alignées puisque ${\displaystyle x=ab.aba.ab.aba=ababa.ababa}$ ; les mots ${\displaystyle aba,ababa,baaba}$ et ${\displaystyle baabab}$ sont tous des germes de ${\displaystyle x}$ : les couvertures par ${\displaystyle aba}$ et ${\displaystyle ababa}$ sont celles de ${\displaystyle x}$ lui-même ; celle par ${\displaystyle baaba}$ est ${\displaystyle baxaba=baaba.baaba.baaba}$ et celle par ${\displaystyle baabab}$ est ${\displaystyle baxabab}$.

Pour le mot ${\displaystyle x=abaababaabaababaabababa}$ de longueur 23, la table ci-dessous donne, pour chaque préfixe, la longueur du plus long bord et la longueur de la plus petite couverture. Ainsi, le préfixe ${\displaystyle abaababaa}$ de longueur 9 a le bord ${\displaystyle abaa}$ de longueur 4, et n'a pas de couverture alignée, alors que ${\displaystyle abaab}$ est le germe d'une ouverture non alignée^[5].

Table des bords et table des couvertures des préfixes de ${\displaystyle x=abaababaabaababaabababa}$

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
x	a	b	a	a	b	a	b	a	a	b	a	a	b	a	b	a	a	b	a	b	a	b	a
B	0	0	1	1	2	3	2	3	4	5	6	4	5	6	7	8	9	10	11	7	8	2	3
C	0	0	0	0	0	3	0	3	0	5	6	0	5	6	0	8	9	10	11	0	8	0	3

Moore et Smyth^[6],[7] donnent un algorithme pour calculer toutes les couvertures d'un mot. Illiopoulos, Moore et Park^[1] présentent un algorithme en ${\displaystyle O(n\log n)}$ pour trouver tous les germes d'un mot de longueur ${\displaystyle n}$. Une présentation générales et donnée dans Christou et al^[8]. Les couvertures optimales ont été étudiées par Mhaskar et Smyth^[9].

Un caractérisation des mots quasi-périodiques a été donnée par L. Mouchard^[10].

Étant donné un mot ${\displaystyle w}$ qui jouera le rôle d'une quasi-période, soient ${\displaystyle b_{1}=\varepsilon ,b_{2},\ldots ,b_{k}}$ les bords de ${\displaystyle w}$ (un bord est un facteur qui est à la fois préfixe est suffixe); et soient ${\displaystyle u_{1},\ldots ,u_{k}}$ les préfixes de ${\displaystyle w}$ tels que ${\displaystyle w=u_{i}b_{i}}$. Alors tout mot ${\displaystyle x}$ quasi-périodique de période ${\displaystyle w}$ est l’image d’un mot sur un alphabet à ${\displaystyle k}$ lettres ${\displaystyle a_{1},\ldots ,a_{k}}$ par le morphisme qui envoie ${\displaystyle a_{i}}$ sur ${\displaystyle u_{i}}$. De manière équivalente, ${\displaystyle x}$ est produit des mots ${\displaystyle u_{i}}$. Par exemple, le mot ${\displaystyle x=aabaaabaabaa}$ est quasi-périodique de quasi-période ${\displaystyle aabaa}$. Il s’écrit comme produit

${\displaystyle x=aaba.aab.aabaa=f(a_{1}a_{2}a_{3})}$,

où le morphisme ${\displaystyle f}$ est défini par ${\displaystyle f(a_{1})=aaba}$, ${\displaystyle f(a_{2})=aab}$, ${\displaystyle f(a_{3})=aab}$.

Une façon équivalente, un mot quasi-périodique peut s'écrire comme produit de suffixes d'une quasi-période ${\displaystyle w}$, en considérant les suffixes ${\displaystyle v_{i}}$ qui complètent un bord : ${\displaystyle w=b_{i}v_{i}}$. Pour ${\displaystyle w=aabaa}$, les suffixes sont ${\displaystyle w}$ lui-même, ${\displaystyle abaa}$ et ${\displaystyle baa}$, et la factorisation est

${\displaystyle x=aabaa.abaa.baa=g(a_{1}a_{2}a_{3})}$,

où le morphisme ${\displaystyle g}$ est défini par ${\displaystyle g(a_{1})=aabaa}$, ${\displaystyle g(a_{2})=abaa}$, ${\displaystyle g(a_{3})=baa}$.

Une couverture améliorée (enhanced en anglais) ${\displaystyle u}$ de ${\displaystyle x}$ est un bord de ${\displaystyle x}$ (c'est-à-dire un préfixe propre qui est aussi un suffixe) qui couvre un nombre maximal de positions en ${\displaystyle x}$, mais pas nécessairement toutes^[11].

Solomon Marcus a étendu la notion de mot quasi-périodique aux mots infinis et a posé à cette occasion diverses questions dans un article au bulletin de l'EATCS^[12],[13] qui a suscité plusieurs travaux subséquents^{[14],[15],[16],[13]}.

L'exposant critique d'un mot infini quasi-périodique a été étudié par Gwenaël Richomme^[17]. L'exposant critique d'un mot est le maximum des exposants des répétitions contenues dans le mot.

On sait, d'après un résultat de Dana Krieger et J. Shallit^[18] que tout nombre réel plus grand que 1 peut être l'exposant critique d'un mot infini. Un mot infini périodique a un exposant critique infini. Il n'en est pas ainsi pour les mots quasi-périodique : il existe des mots infinis quasi-périodiques dont l'exposant critique est ${\displaystyle 2+\varepsilon }$ pour tout ${\displaystyle \varepsilon >0}$. Le plus petit exposant critique d'un mot infini binaire quasi-périodique est 7/3^[17], et tout mot infini binaire contient une répétition d'exposant au moins 7/3. Ces résultats reposent sur des propriétés décrites par J. Karhumäki et J. Shallit^[19].

On peut faire le lien entre l'exposant critique et la notion de run. Un run est une répétition maximale dans un mot, pourvu que l'exposant en soit au moins égal à 2. Par exemple, le mot ${\displaystyle ababaabaaa}$ contient les runs ${\displaystyle ababa}$, ${\displaystyle aa}$, ${\displaystyle abaabaa}$ et ${\displaystyle aaa}$ d'exposants 5/2, 2, 7/3 et 3 respectivement. L'exposant critique de ce mot est donc 3.

La table des couvertures est l'analogue, pour les quasi-périodes, de la table des bords d'un mot : la table des bords d'un mot ${\displaystyle x}$ de longueur ${\displaystyle n}$ est la table ${\displaystyle B}$ à ${\displaystyle n}$ éléments donnant, pour chaque indice ${\displaystyle i}$, le plus long bord du préfixe de longueur ${\displaystyle i}$ du mot ${\displaystyle x}$. Par analogie, table des couvertures d'un mot ${\displaystyle x}$ de longueur ${\displaystyle n}$ est la table ${\displaystyle C}$ à ${\displaystyle n}$ éléments donnant, pour chaque indice ${\displaystyle i}$, la plus longue couverture alignée du préfixe de longueur ${\displaystyle i}$ du mot ${\displaystyle x}$, si ce préfixe possède un mot couvrant, et 0 sinon^[5].

Par exemple^[5], pour le mot ${\displaystyle x=abaababaabaababaabababa}$ de longueur 23, le préfixe ${\displaystyle abaababaa}$ de longueur 9 a le bord ${\displaystyle abaa}$ de longueur 4, et n'a pas de couverture alignée, alors que ${\displaystyle abaab}$ est le germe d'une ouverture non alignée.

Table des bords et table des couvertures

i	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23
x	a	b	a	a	b	a	b	a	a	b	a	a	b	a	b	a	a	b	a	b	a	b	a
B	0	0	1	1	2	3	2	3	4	5	6	4	5	6	7	8	9	10	11	7	8	2	3
C	0	0	0	0	0	3	0	3	0	5	6	0	5	6	0	8	9	10	11	0	8	0	3

• Mot infini
• Mot sturmien
• Exposant critique
• Mot de Lyndon
• Répétitions dans un mot
• Algorithme de recherche de sous-chaîne
• Tableau des suffixes

• Portail de l'informatique théorique