Mot quasi-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}$.

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