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.

Motivation[modifier | modifier le code]

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 $u$ d'un mot $x$ rend compte de la nature répétitive d'un mot $x$ , puisque $x$ est construit par la concaténation de copies du mot $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 $x$ est une facteur propre $u$ de $x$ tel que $x$ peut être construit à partir d'instances éventuellement chevauchantes de $u$ .

Définitions[modifier | modifier le code]

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

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

Couverture alignée[modifier | modifier le code]

Étant donné un mot $x$ , un facteur $w$ de $x$ tel que $x$ peut être construit par concaténation et superpositions de $w$ fournit une couverture alignée de $x$ ^[1]. Le mot $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 $x$ est quasi-périodique.

Dans cette définition, le mot $w$ est à la fois préfixe et suffixe de $x$ . Par exemple, le mot $x=abaabababaaba$ est quasi-périodique de mot couvrant $w=aba$ : $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 $w=aabaa$ , les plus petits mots quasi-périodiques de période $w$ sont : $aabaabaa$ ,
$aabaaabaa$ ,
$aabaabaabaa$ ,
$aabaabaaabaa$ ,
$aabaababaabaa$ . Le mot $aabaabaaba$ ne figure pas dans cette liste parce qu'il ne finit pas par $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 $O(n\log ^{2}n)$ pour calculer tous les mots couvrants maximaux d'un mot de longueur $n$ .

Couverture[modifier | modifier le code]

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 $x=abaabaab$ est périodique de période 3 et est quasi-périodique de germe $abaab$ ; de même $x=abcabcabca$ est quasi-périodique de période $abca$ : $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 $x$ est une couverture alignée d'un sur-mot (superstring) $y$ de $x$ , c'est-à-dire d'un mot $y$ qui a $x$ en facteur. Par exemple, $w=abca$ est un germe de $x=abc.abca.abc$ . Le mot $w$ est un germe (seed) de $x$ . Un germe de longueur minimale n'est pas forcément unique ; ainsi $abababa$ a les deux germes $ab$ et $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.

Exemples[modifier | modifier le code]

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

Pour le mot $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 $abaababaa$ de longueur 9 a le bord $abaa$ de longueur 4, et n'a pas de couverture alignée, alors que $abaab$ est le germe d'une ouverture non alignée^[5].

Table des bords et table des couvertures des préfixes de $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 $O(n\log n)$ pour trouver tous les germes d'un mot de longueur $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].

Caractérisation[modifier | modifier le code]

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

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

x=aaba.aab.aabaa=f(a_{1}a_{2}a_{3})

,

où le morphisme $f$ est défini par $f(a_{1})=aaba$ , $f(a_{2})=aab$ , $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 $w$ , en considérant les suffixes $v_{i}$ qui complètent un bord : $w=b_{i}v_{i}$ . Pour $w=aabaa$ , les suffixes sont $w$ lui-même, $abaa$ et $baa$ , et la factorisation est

x=aabaa.abaa.baa=g(a_{1}a_{2}a_{3})

,

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

Variantes[modifier | modifier le code]

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

Mots infinis[modifier | modifier le code]

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 $2+\varepsilon$ pour tout $\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 $ababaabaaa$ contient les runs $ababa$ , $aa$ , $abaabaa$ et $aaa$ d'exposants 5/2, 2, 7/3 et 3 respectivement. L'exposant critique de ce mot est donc 3.

Table des couvertures[modifier | modifier le code]

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 $x$ de longueur $n$ est la table $B$ à $n$ éléments donnant, pour chaque indice $i$ , le plus long bord du préfixe de longueur $i$ du mot $x$ . Par analogie, table des couvertures d'un mot $x$ de longueur $n$ est la table $C$ à $n$ éléments donnant, pour chaque indice $i$ , la plus longue couverture alignée du préfixe de longueur $i$ du mot $x$ , si ce préfixe possède un mot couvrant, et 0 sinon^[5].

Par exemple^[5], pour le mot $x=abaababaabaababaabababa$ de longueur 23, le préfixe $abaababaa$ de longueur 9 a le bord $abaa$ de longueur 4, et n'a pas de couverture alignée, alors que $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

Notes et références[modifier | modifier le code]

↑ ^{a et b} Costas S. Iliopoulos, D. W. G. Moore et K. Park, « Covering strings », Algorithmica, vol. 16, n^o 3,‎ 1996, p. 288–297 (ISSN 0178-4617, DOI 10.1007/BF01955677).
↑ Alberto Apostolico, Martin Farach et Costas S. Iliopoulos, « Optimal superprimitivity testing for strings », Information Processing Letters, vol. 39, n^o 1,‎ 1991, p. 17–20 (ISSN 0020-0190, DOI 10.1016/0020-0190(91)90056-N)
↑ Dany Breslauer, « An on-line string superprimitivity test », Information Processing Letters, vol. 44, n^o 6,‎ 1992, p. 345–347 (ISSN 0020-0190, DOI 10.1016/0020-0190(92)90111-8).
↑ ^{a et b} Alberto Apostolico et Andrzej Ehrenfeucht, « Efficient detection of quasiperiodicities in strings », Theoretical Computer Science, vol. 119, n^o 2,‎ 1993, p. 247–265 (DOI 10.1016/0304-3975(93)90159-Q).
↑ ^{a b et c} Yin Li et William F. Smyth, « Computing the cover array in linear time », Algorithmica, vol. 32, n^o 1,‎ 2002, p. 95-106 (ISSN 0178-4617, DOI 10.1007/s00453-001-0062-2)
↑ Dennis W. G. Moore et William F. Smyth, « An optimal algorithm to compute all the covers of a string », Information Processing Letters, vol. 50, n^o 5,‎ 1994, p. 239–246 (ISSN 0020-0190, DOI 10.1016/0020-0190(94)00045-X).
↑ Dennis W. G. Moore et William F. Smyth, « A Correction to "An Optimal Algorithm to Compute all the Covers of a String" », Information Processing Letters, vol. 54, n^o 2,‎ 1995, p. 101-103 (DOI 10.1016/0020-0190(94)00235-Q)
↑ Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder et Tomasz Waleń, « Efficient Seeds Computation Revisited », Lecture Notes in Computer Science, vol. 6661,‎ 2011, p. 350–363 (ISSN 0302-9743, DOI 10.1007/978-3-642-21458-5_30)
↑ Neerja Mhaskar et William F. Smyth, « String covering with optimal covers », Journal of Discrete Algorithms, vol. 51,‎ 2018, p. 26–38 (ISSN 1570-8667, DOI 10.1016/j.jda.2018.09.003)
↑ Laurent Mouchard, « Normal forms of quasiperiodic strings », Theoretical Computer Science, vol. 249, n^o 2,‎ 2000, p. 313–324 (DOI 10.1016/S0304-3975(00)00065-7).
↑ Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth et Wojciech Tyczyński, « Enhanced string covering », Theoretical Computer Science, vol. 506,‎ 2013, p. 102–114 (ISSN 0304-3975, DOI 10.1016/j.tcs.2013.08.013)
↑ Solomon Marcus, « Quasiperiodic Infinite Words », Bulletin of the EATCS, n^o 82,‎ 2004, p. 170-174.
↑ ^{a et b} Florence Levé et Gwenaël Richomme, « On quasiperiodic morphisms », Proceedings of the 9th International Conference on Words,‎ 2013, p. 181-192 (DOI 10.1007/978-3-642-40579-2_20).
↑ Amy Glen, Florence Levé et Gwénaël Richomme, « Quasiperiodic and Lyndon episturmian words », Theoretical Computer Science, vol. 409, n^o 3,‎ 2008, p. 578–600 (DOI 10.1016/j.tcs.2008.09.056).
↑ Florence Levé et Gwenaël Richomme, « Quasiperiodic infinite words: some answers », Bulletin of the EATCS, n^o 84,‎ 2004, p. 128-138.
↑ Florence Levé et Gwenaël Richomme, « Quasiperiodic Sturmian words and morphisms », Theoretical Computer Science, vol. 372, n^o 1,‎ 2007, p. 15–25 (DOI 10.1016/j.tcs.2006.10.034).
↑ ^{a et b} Gwenaël Richomme, « Minimal critical exponent of quasiperiodic words », Theoretical Computer Science, vol. 548,‎ 2014, p. 117–122 (DOI 10.1016/j.tcs.2014.06.039).
↑ Dalia Krieger et Jeffrey Shallit, « Every real number greater than 1 is a critical exponent », Theoretical Computer Science, vol. 381, n^os 1-3,‎ 2007, p. 177–182 (DOI 10.1016/j.tcs.2007.04.037)
↑ Juhani Karhumäki et Jeffrey Shallit, « Polynomial versus exponential growth in repetition-free binary words », Journal of Combinatorial Theory, Series A, vol. 105, n^o 2,‎ 2004, p. 335–347 (DOI 10.1016/j.jcta.2003.12.004).

Articles liés[modifier | modifier le code]

Portail de l'informatique théorique

[IliopoulosMoore1996-1] {a et b} Costas S. Iliopoulos, D. W. G. Moore et K. Park, « Covering strings », Algorithmica, vol. 16, n^o 3,‎ 1996, p. 288–297 (ISSN 0178-4617, DOI 10.1007/BF01955677).

[ApostolicoFarach1991-2] Alberto Apostolico, Martin Farach et Costas S. Iliopoulos, « Optimal superprimitivity testing for strings », Information Processing Letters, vol. 39, n^o 1,‎ 1991, p. 17–20 (ISSN 0020-0190, DOI 10.1016/0020-0190(91)90056-N)

[Breslauer1992-3] Dany Breslauer, « An on-line string superprimitivity test », Information Processing Letters, vol. 44, n^o 6,‎ 1992, p. 345–347 (ISSN 0020-0190, DOI 10.1016/0020-0190(92)90111-8).

[ApostolicoEhrenfeucht1993-4] {a et b} Alberto Apostolico et Andrzej Ehrenfeucht, « Efficient detection of quasiperiodicities in strings », Theoretical Computer Science, vol. 119, n^o 2,‎ 1993, p. 247–265 (DOI 10.1016/0304-3975(93)90159-Q).

[LiSmyth2002-5] {a b et c} Yin Li et William F. Smyth, « Computing the cover array in linear time », Algorithmica, vol. 32, n^o 1,‎ 2002, p. 95-106 (ISSN 0178-4617, DOI 10.1007/s00453-001-0062-2)

[MooreSmyth1994-6] Dennis W. G. Moore et William F. Smyth, « An optimal algorithm to compute all the covers of a string », Information Processing Letters, vol. 50, n^o 5,‎ 1994, p. 239–246 (ISSN 0020-0190, DOI 10.1016/0020-0190(94)00045-X).

[MooreSmyth1995-7] Dennis W. G. Moore et William F. Smyth, « A Correction to "An Optimal Algorithm to Compute all the Covers of a String" », Information Processing Letters, vol. 54, n^o 2,‎ 1995, p. 101-103 (DOI 10.1016/0020-0190(94)00235-Q)

[ChristouCrochemore2011-8] Michalis Christou, Maxime Crochemore, Costas S. Iliopoulos, Marcin Kubica, Solon P. Pissis, Jakub Radoszewski, Wojciech Rytter, Bartosz Szreder et Tomasz Waleń, « Efficient Seeds Computation Revisited », Lecture Notes in Computer Science, vol. 6661,‎ 2011, p. 350–363 (ISSN 0302-9743, DOI 10.1007/978-3-642-21458-5_30)

[MhaskarSmyth2018-9] Neerja Mhaskar et William F. Smyth, « String covering with optimal covers », Journal of Discrete Algorithms, vol. 51,‎ 2018, p. 26–38 (ISSN 1570-8667, DOI 10.1016/j.jda.2018.09.003)

[Mouchard2000-10] Laurent Mouchard, « Normal forms of quasiperiodic strings », Theoretical Computer Science, vol. 249, n^o 2,‎ 2000, p. 313–324 (DOI 10.1016/S0304-3975(00)00065-7).

[FlouriIliopoulos2013-11] Tomáš Flouri, Costas S. Iliopoulos, Tomasz Kociumaka, Solon P. Pissis, Simon J. Puglisi, William F. Smyth et Wojciech Tyczyński, « Enhanced string covering », Theoretical Computer Science, vol. 506,‎ 2013, p. 102–114 (ISSN 0304-3975, DOI 10.1016/j.tcs.2013.08.013)

[Marcus2004-12] Solomon Marcus, « Quasiperiodic Infinite Words », Bulletin of the EATCS, n^o 82,‎ 2004, p. 170-174.

[LevéRichomme2013-13] {a et b} Florence Levé et Gwenaël Richomme, « On quasiperiodic morphisms », Proceedings of the 9th International Conference on Words,‎ 2013, p. 181-192 (DOI 10.1007/978-3-642-40579-2_20).

[GlenLevé2008-14] Amy Glen, Florence Levé et Gwénaël Richomme, « Quasiperiodic and Lyndon episturmian words », Theoretical Computer Science, vol. 409, n^o 3,‎ 2008, p. 578–600 (DOI 10.1016/j.tcs.2008.09.056).

[LevéRichomme2004-15] Florence Levé et Gwenaël Richomme, « Quasiperiodic infinite words: some answers », Bulletin of the EATCS, n^o 84,‎ 2004, p. 128-138.

[LevéRichomme2007-16] Florence Levé et Gwenaël Richomme, « Quasiperiodic Sturmian words and morphisms », Theoretical Computer Science, vol. 372, n^o 1,‎ 2007, p. 15–25 (DOI 10.1016/j.tcs.2006.10.034).

[Richomme2014-17] {a et b} Gwenaël Richomme, « Minimal critical exponent of quasiperiodic words », Theoretical Computer Science, vol. 548,‎ 2014, p. 117–122 (DOI 10.1016/j.tcs.2014.06.039).

[KriegerShallit2007-18] Dalia Krieger et Jeffrey Shallit, « Every real number greater than 1 is a critical exponent », Theoretical Computer Science, vol. 381, n^os 1-3,‎ 2007, p. 177–182 (DOI 10.1016/j.tcs.2007.04.037)

[KarhumäkiShallit2004-19] Juhani Karhumäki et Jeffrey Shallit, « Polynomial versus exponential growth in repetition-free binary words », Journal of Combinatorial Theory, Series A, vol. 105, n^o 2,‎ 2004, p. 335–347 (DOI 10.1016/j.jcta.2003.12.004).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]