Accueil🇫🇷Chercher

Répétition inévitable

En combinatoire des mots, une répétition est une suite de symboles qui se répète plusieurs fois consécutivement. Par exemple, le mot répétition lui-même contient la répétition titi, formé de deux occurrences consécutives du mot ti. L'étude des répétitions a des applications importantes en biologie, où on les retrouve sous le terme général de répétition en tandem, en compression des données à l’aide de dictionnaires, comme dans l'algorithme de Lempel-Ziv-Welch. Une répétition évitable est une répétition que l’on peut éviter dans certains cas, une répétition inévitable est une répétition qui apparaîtra nécessairement à un moment donné. Une généralisation de cette notion est celle de motif inévitable.

Par exemple, un cube xxx est évitable sur 2 lettres, un carré xx est inévitable sur 2 lettres, mais est évitable sur 3 lettres : ce sont les mots sans carré. Le motif xyx est inévitable, même sur 2 lettres.

Période, exposant, répétition et sesquipuissance

Un entier est une période du mot si pour . Dans ce cas, est une puissance (rationnelle) de . L'exposant de cette puissance est le nombre . Ainsi, l'entier 5 est la période minimale de , et . Une sesquipuissance est un mot dont l'exposant est strictement supérieur à 1. Le mot est aussi une puissance fractionnaire de , puisque . Quand on cherche des puissances (fractionnaires) dans un mot, on considère souvent la plus petite période, et donc l'exposant le plus élevé. En posant , on a , où est l'exposant et est le préfixe de de longueur . On peut aussi définir la période (minimale) d'un mot comme la longueur du plus court préfixe de telle que est préfixe du mot infini .

Le terme de répétition est quelquefois réservé aux mots d'exposant valant au moins deux. L'existence d'un seuil pour les répétitions fractionnaires a été conjecturé par Françoise Dejean en 1972 ; la démonstration de ce fait est le théorème de Dejean.

Répétition inévitable

Un carré xx est inévitable sur 2 lettres : tout mot de longueur 4 sur deux lettres, disons a et b, contient un carré. Ceci est clair si le mot contient deux occurrences consécutives de la même lettres. Les autres mots sont abab et baba, qui sont des carrés.

Un carré xx est inévitable sur 3 lettres : c'est une construction du mathématicien norvégien Axel Thue qui a, en premier, donné un exemple d'un mot sans carré, mot infini sur 3 lettres ne contenant pas de carré.

Répétition abélienne

Une répétition abélienne ou puissance abélienne est une suite de mots consécutifs de même longueur qui sont égaux entre eux à une permutation près. En d'autres termes, les blocs consécutifs composant une puissance abélienne sont des anagrammes les uns des autres. Un carré abélien est une répétition abélienne composée de deux blocs, donc un mot xy, où y est une permutation de x.

Paul Erdős a posé la question de l'existence d'un mot infini sans carré abélien en 1961[1]. Une réponse positive a été apportée successivement pour des alphabets à 25 symboles[2], puis à 5 lettres[3] et enfin à 4 lettres par Veikko Keränen en 1992[4] - [5]. Dekking a montré que les cubes abéliens sont évitables sur 3 lettres au moyen du mot infini engendré par itération à partir de 0 par le morphisme . Il a aussi montré que les cubes abéliens sont inévitables sur 2 lettres et que les puissances abéliennes d'ordre 4 sont évitables sur 2 lettres[6].

Un problème voisin est celui des puissances -abéliennes. Deux mots et sont dits -abéliennement équivalents s'ils possèdent les mêmes facteurs de longueur au plus . Il est commode de noter cette propriété par . Pour , on retrouve l'équivalence commutative usuelle. Une puissance -abélienne d'ordre est un mot composé de mots -abéliennement équivalents, donc avec . On peut démontrer[7] l'existence d'un mot binaire infini sans cubes 2-abéliens et d'un mot ternaire infini sans carrés 3-abéliens. Pour ce faire, Michaël Rao donne des conditions suffisantes pour qu'un morphisme préserve les mots sans puissance -abélienne d'ordre et il construit des morphismes qui satisfont ces conditions. De plus, ces constructions montrent que le nombre de tels mots croît exponentiellement. En particulier, le nombre de mots sans cube abélien croît au moins comme

Répétition additive

Lorsque l'alphabet est composé lui-même de nombres, on peut replacer la condition sur les symboles par une condition sur la somme des symboles constituant les facteurs. Ainsi, un carré additif est un mot xy, où x et y ont même longueur et où la somme des symboles de x est égale à la somme des symboles de y. Par exemple, sur l’alphabet {1,2,3,4}, le mot 1423 est un carré additif parce que 1+4=2+3.

Plus généralement, un mot est une puissance additive s'il est composé de blocs consécutifs de même longueur et de même somme. Ainsi, un mot est une puissance additive d'ordre k, ou une k-puissance additive, si les ont même longueur et si , où est la somme des symboles de .

Une k-puissance additive est évitable sur un alphabet donné s'il existe un mot infini sur cet alphabet qui ne contient pas de k-puissance additive. La première mention du problème d'existence de mots sans k-puissance additive remonte à 1994[8] - [9].

Les cubes additifs sont évitables

Un important résultat sur les cubes additifs est que les cubes additifs sont évitables sur l'alphabet A={0,1,3,4}[9]. Pour établir ce résultat, il faut exhiber un mot infini sur cet alphabet et montrer qu'il est sans cube additif. Le mot construit par les auteurs de l’article est obtenu en itérant à partir de 0 le morphisme uniforme donné par : . Le mot obtenu est purement morphique, il commence par

Notes et références

  1. Paul Erdős, « Some unsolved problems », Publ. Math. Inst. Hung. Acad. Sci., Ser. A, vol. 6, , p. 221–254 (zbMATH 100.02001, lire en ligne).
  2. A. A. Evdokimov, « Strongly asymmetric sequences generated by a finite number of symbols », Dokl. Akad. Nauk SSSR, vol. 179, , p. 1268–1271. Traduction anglaise dans Soviet Math. Dokl., Vol. 9 (1968), p. 536–539.
  3. P. A. B. Pleasants, « Non-repetitive sequences », Proc. Cambridge Philos. Soc., vol. 68, , p. 267–274.
  4. Veikko Keränen, « Abelian squares are avoidable on 4 letters », dans Automata, languages and programming (ICALP), vol. 623, coll. « Lecture Notes in Comput. Sci. », , 41–52 p..
  5. Veikko Keränen, « A powerful abelian square-free substitution over 4 letters », Theoretical Computer Science, vol. 410, nos 38-40, , p. 3893-3900 (DOI 10.1016/j.tcs.2009.05.027, lire en ligne).
  6. F. M. Dekking, « Strongly non-repetitive sequences and progression-free sets », J. Combin. Theory. Ser. A, vol. 27, , p. 181–185.
  7. Michaël Rao, « On some generalizations of abelian power avoidability », Theoretical Computer Science, vol. 601, , p. 39–46 (ISSN 0304-3975, DOI 10.1016/j.tcs.2015.07.026).
  8. Guiseppe Pirillo et Stephano Varricchio, « On uniformly repetitive semigroups », Semigroup Forum, vol. 49, , p. 125–129
  9. (en) Julien Cassaigne, James D. Currie, Luke Schaeffer et Jeffrey Shallit, « Avoiding Three Consecutive Blocks of the Same Size and Same Sum », Journal of the ACM, vol. 61, no 2, , p. 1-17, article no 10 (DOI 10.1145/2590775, arXiv 1106.5204).

Articles liés

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.