En combinatoire, et notamment en combinatoire des mots, un carré est un mot composé de deux parties égales consécutives, comme bonbon ou papa. En bio-informatique, un carré est appelé une répétition en tandem. Un mot sans facteur carré ou plus simplement un mot sans carré est un mot qui ne contient pas de facteur carré. Par exemple, le mot répétition contient le carré titi ; en revanche, le mot consécutivement est un mot sans carré. L'étude des mots sans carré fait partie, plus généralement, de l'étude des répétitions dans les mots, et de la possibilité de les éviter. On parle alors de répétitions évitables ou inévitables.
Il existe des mots infinis sans carré sur tout alphabet d'au moins trois lettres, comme l'a prouvé Axel Thue[1],[2]. Sur un alphabet à deux lettres, un tel mot n'existe pas. Le mot de Prouhet-Thue-Morse contient des carrés, en revanche il est sans cube.
Une méthode fréquemment utilisée par construire des mots infinis sans carré, sans cube ou sans puissance plus élevée est par itération d'un morphisme. Si ce morphisme a la propriété de transformer une mot fini sans carré, sans cube ou sans puissance plus élevée en un mot de même nature, on parle d'un morphisme sans carré, sans cube ou sans puissance plus élevée.
Premiers exemples
- Sur un alphabet à deux lettres , il n'existe que six mots sans carré non vides : ce sont les mots .
- Sur un alphabet à trois lettres , et partant de la lettre , on remplace
- par , par , par .
- On alors obtient successivement
- En itérant et en prenant le point fixe de cette opération, on obtient le mot infini qui commence par
- .
- Ce mot est sans carré. Cette construction est donnée par Marshall Hall Jr.[3]. Dans la terminologie des répétitions, les carrés sont inévitables sur 2 lettres, mais évitables sur plus de 2 lettres.
Les constructions de Thue
Les premières constructions de Thue datent de 1906 et 1912. Plusieurs auteurs les ont, de façon indépendante, retrouvées, ou ont trouvé d'autres constructions. Les articles de Thue, même s'ils étaient écrits en allemand qui à l'époque était l'une des langues scientifiques par excellence ont été publiés dans un journal peu connu, et n'ont donc pas été largement reconnus.
Les constructions de Thue (1906)
Thue donne, dans son premier article[1] datant de 1906, plusieurs constructions de mots infinis sans carré.
Un premier mot sans carré, sur un alphabet à 4 lettres, est obtenu comme suit : on part du mot , et on insère la lettre entre deux lettres du mot, à 4 places différentes. Ces 4 mots sont pris pour définir un morphisme :
En itérant à partir de la lettre a, on obtient le mot infini (les barres verticales sont censées faciliter la lecture) :
- .
Le symbole sert de « marqueur » qui permet de retrouver la lettre qui a engendré un bloc donné.
Thue donne un autre mot sans carré, sur trois lettres cette fois-ci, obtenu comme suit : on remplace, dans un mot sans carré sur , les lettres selon les règles suivantes :
- si la lettre avant est
- si la lettre avant est
En partant de a, on obtient
- .
La construction de Thue (1912)
Dans son long article[2], Axel Thue poursuit le but de classer toutes les suites sans carré, sans toutefois y parvenir complètement. Durant cette étude, il construit un mot sans carré à partir de la suite de Prouhet-Thue-Morse :
- .
Il observe que, comme il n'y a pas de bloc dans la suite, deux symboles consécutifs sont séparés par 0, 1, ou 2 symboles . Il suffit de reporter la séquence de ces nombres pour obtenir une suite sur trois symboles :
- .
En remplaçant par , par et par , on retrouve la suite mentionnée plus haut. Cette suite est parfois appelée la suite ternaire de Thue-Morse. La construction a été retrouvée en 1963 par C. H. Braunholtz[4].
Autres constructions
La suite asymétrique d'Arshon (1937)
Dans un article en russe[5] mais avec un long résumé en français, le mathématicien russe C. E. Arshon propose une construction générale qui, dans le cas ternaire, donne un mot infini sans carré (qu'il appelle asymétrique). Dans le cas binaire, une version simplifiée redonne la suite de Prouhet-Thue-Morse. Arshon considère les deux morphismes :
Le premier sert pour produire des mots à partir de symboles en position impaire dans un mot, le deuxième pour les symboles en position paire. On commence par le mot
Le premier est en position impaire 1, et il produit , le en position 2 produit , et le troisième symbole, en position impaire, produit . On obtient la suite (les barres verticales doivent améliorer la lisibilité) :
On continue : le en position 4 produit , le en position 5 produit , le en position 6 produit , etc. On construit ainsi une suite débutant par :
Arshon prouve que ce mot est sans carré. Cette suite est 3-automatique : on prend le morphisme sur 6 lettres donné par
- .
Ce morphisme 3-uniforme engendre le mot infini
où les lettres en position paire sont barrées. Dans un deuxième temps, on « efface » les barres sur les lettres par le morphisme lettre-à-lettre qui identifie une lettre et sa copie barrée.
La construction de Morse et Hedlund (1944)
Dans leur article[6], Morse et Hedlund partent, comme Thue, de la suite de Prouhet-Thue-Morse :
- .
Contrairement à Thue, ils remplacent deux bits consécutifs par le nombre qu'il représentent en binaire, soit
puis ils identifient et (en d'autres termes, ils opèrent modulo 3). La suite obtenue est :
- .
C'est la suite ternaire de Thue-Morse, au codage près. On obtient le même mot différemment, en itérant le morphisme sur 4 lettres donné par :
et en identifiant ensuite et . L'intérêt de cette construction est de montrer que le mot ternaire de Thue-Morse est une suite automatique.
Le morphisme de Hawkins et Mientka (1956)
Ces deux auteurs proposent[7] le morphisme suivant :
et ils prouvent qu'en itérant à partir de la lettre , on obtient un mot infini sans carré.
Les perles de John Leech (1957)
Dans une courte note[8], John Leech propose la construction suivante. On itère le morphisme défini par
L'image de chaque lettre est le mot transformé par . En itérant à partir de , on obtient
En fait, Leech est intéressé par la construction d'une suite biinfinie sans carré. Pour cela, il recentre chaque mot sur la lettre du milieu. Pour obtenir une convergence, il faut modifier le morphisme de sorte que la lettre centrale de l'image de soit etc. On prend donc
L'itération donne :
La construction de Zech (1958)
Theodor Zech[9] donne le morphisme
Le mot infini est obtenu en itérant à partir de par exemple. La preuve est facilitée par le fait que les trois images se terminent toutes par .
La construction sans simplification de Dean (1963)
Richard Dean[10] construit une suite sans carré sur quatre symboles avec la propriété supplémentaire que deux symboles appareillés ne peuvent se suivre. De façon plus imagée, si les quatre sont , la suite ne contient pas les blocs , , et . Pour simplifier l'exposé, Dean choisit les symboles et construit une suite sans carré sans les facteurs . Il obtient ceci en imposant que les symboles en position paire dans la suite sont des symboles pairs, et les symboles en position impaire sont impairs. La suite est la limite de la suite de mots obtenue comme suite: On pose . Chaque est un mot de longueur qui est factorisé en quatre mot de longueur notés de sorte que
- .
Le mot est défini par
- .
On obtient
En fait, on se convainc très vite que les mots s'obtiennent en itérant, à partir de , le morphisme
D'autres constructions, ou les mêmes, ont été données par Kurosaki, Shyr, Dejean.
Le mot infini de Dean a fait l'objet d'une étude par Golnaz Badkobeh, Tero Harju, Pascal Ochem et Matthieu Rosenfeld[11]. Les auteurs considèrent les mots de Dean finis qu'ils définissent comme des mots réduits sans carré. Ils montrent que si w est un mot de Dean de longueur au moins 59 alors il y a au plus six mots réduits de longueur 3 qui sont évités par w. Ils construisent un mot de Dean infini évitant six mots réduits de longueur 3. Ils construisent également des mots de Dean infinis ayant un exposant critique bas et qui évitent moins de mots réduits de longueur 3. Enfin, ils montrent que la fréquence minimale d'une lettre dans un mot de Dean est de 8/59 et que le taux de croissance est proche de 1,45818.
Morphismes sans carré
Un morphisme qui transforme un mot sans carré en un mot sans carré, donc qui préserve les mots sans carrés, est appelé lui-même un morphisme sans carré. Si est un tel morphisme, on construit une suite de mots sans carré en partant d'une lettre , et appliquant le morphisme indéfiniment :
- .
Si les mots deviennent de plus en plus long, et si de plus le mot commence par , le mot infini, souvent noté
dont tous les sont préfixes, est un mot infini sans carré. Plus généralement, un morphisme sans puissance -ième est un morphisme qui préserve les mots sans puissances -ième et à nouveau, le mot infini est sans puissance -ième.
Un théorème d'Axel Thue et de Maxime Crochemore
Le théorème suivant, démontré par Axel Thue, permet de démontrer simplement pour de nombreux exemples de morphismes qu'ils engendrent des mots sans carrés. Dans cet énoncé et dans la suite, on ignore systématiquement le mot vide qui ne joue pas de rôle dans ce contexte. Un morphisme est infixe si aucun mot n'est facteur d'un mot , pour deux lettres . Une démonstration est donnée par Bean, Ehrenfeucht et McNulty[12], et aussi par Lothaire[13].
Théorème (Thue (1912)[14]) — Soit un morphisme qui est infixe et tel que est sans carré pour tout mot sans carré de longueur 3. Alors est un morphisme sans carré.
La condition d'être infixe est notamment réalisée par les morphismes uniformes, pourvu qu'ils soient injectifs sur l'alphabet.
Maxime Crochemore a étendu ce théorème à des morphismes plus généraux.
Théorème (Crochemore (1982)[15]) — Soit un morphisme, et soient
- et .
Si est sans carré pour tout mot sans carré de longueur
- ,
alors est un morphisme sans carré.
Dans le cas des morphismes uniformes, on retrouve la borne de Thue.
Sur un alphabet à 3 lettres, on peut donner une formulation encore plus précise :
Théorème (Crochemore (1982)[15]) — Si est un morphisme sur un alphabet à trois lettres tel que est sans carré pour tout mot sans carré de longueur 5, est un morphisme sans carré.
Le morphisme défini par
préserve les mots sans carré de longueur au plus 4, mais contient le carré . Ceci montre que l'on ne peut pas remplacer l'entier 5 par 4 dans le théorème précédent.
Un tel résultat n'existe pas pour des alphabets plus grands. Si l'alphabet A au plus de 3 lettres, il existe pour tout n des morphismes qui préservent des mots sans carrés de longueur n sans être des morphismes sans carré. Il en est ainsi du morphisme défini par
- ,
où est un mot sans carré de longueur sur les trois lettres . Le mot est un mot sans carré, de longueur , et contient un carré, donc n’est pas un morphisme sans carré. Mais on peut vérifier que préserve les mots sans carré de longueur .
Exemples
Les morphismes et donnés par et sont tous deux sans carré[12],[2]. La somme des longueurs des images des lettres est dans les deux cas égale à 18 (5+6+7). Il a été prouvé par Arturo Carpi[16] qu'il n existe pas de morphismes sans carré dont la somme des longueurs des images des lettres est plus petite.
Puissances supérieures
Exemples
Voici quelques exemples de morphismes sans puissance supérieures.
Le morphisme de Prouhet-Thue-Morse
est sans puissance -ième pour tout k>2.
Le morphisme de Fibonacci
engendre le mot de Fibonacci . Ce mot est sans puissance -ième, mais le morphisme de Fibonacci lui-même n'est pas un morphisme sans puissance 4e puisque
Un exemple de Bean, Ehrenfeucht et McNulty[12] ; le morphisme défini par
est sans carré mais n'est pas sans cube.
L'existence de morphismes sans puissance a été prouvée[12] : pour tout alphabet ternaire, il existe un morphisme sans carré de l'alphabet dans lui-même, pour tout alphabet binaire, il existe un morphisme sans cube de l’alphabet dans lui-même.
Théorème (Bean, Ehrenfeucht, McNulty 1979[12]) — Un morphisme infixe, sans carré, et tel que l'image d'une lettre, si elle n'est pas une lettre, ne commence et ne finit par pas la même lettre est aussi sans puissance -ième pour tout .
Morphismes sans cube
Le cas des morphismes sans cube diffère de celui des autres morphismes sans puissance -ième ; être sans cube une condition moins restrictive que d'être sans carré. On a le résultat suivant :
Théorème (Wlazinski (2018)[17]) — Un morphisme uniforme sans cube est aussi un morphisme sans puissance -ième pour tout .
L'existence d'un tel morphisme uniforme, sur un alphabet binaire, a été prouvé notamment par Currie et Rampersand[18].
Mots sans cube avec transitions
Un cas de régularité sur les mots sans cubes a été établi par Elena A. Petrova et Arseny M. Shur[19].
Théorème — Pour toute paire de mots sans cube ayant la propriété que peut être prolongé à gauche en un mot infini sans cube, et peut être prolongé à droite en un mot infini sans cube, il existe un mot de « transition » sur le même alphabet tel que est sans cube. Ce résultat vaut aussi pour des alphabets binaires.
Les auteurs montrent que ce résultat implique l'existence de mots infinis sans cube ayant une complexité en facteurs très élevés.
Suite k-Thue
Une -sous-suite d'une suite est toute une sous-suite d'éléments pris à distance . Une suite k-Thue une suite dans laquelle chaque sous-suite, pour , est non répétitive, c'est-à-dire qu'elle ne contient pas de sous-suites égales consécutives. Une suite de 1-Thue est une suite sans facteur carré. Par exemple,
- a b d c b c
est une suite sans carré, donc 1-Thue, mais elle n'est pas 2-Thue parce que la 2-sous-suite b c c contient un carré. De même,
- a b c a d b
est une suite sans carré, mais elle n'est pas 3-Thue à cause de la 3-sous-suite a a.
La notion de suite k-Thue a été introduite par Currie et Simpson[20]. À leur suite Grytczuk a proposé[21] la conjecture selon laquelle, pour tout , il suffit de symboles pour construire une suite de -Thue de longueur arbitraire. Jusqu'à présent (2020), la conjecture a été confirmée pour [22].
Nombre de mots sans carré
- Le nombre de mots ternaires sans carré de longueur 1, 2, … est la suite A006156 de l'OEIS. Elle commence par :
- Le nombre de mots sur quatre lettres sans carré de longueur 1, 2, … est la suite A051041 de l'OEIS. Elle commence par :
Notons le nombre de mots sans carré de longueur sur un alphabet à lettres. On sait depuis longtemps que croît exponentiellement pour . On connaît maintenant[23] un très bon encadrement pour ces valeurs. On a par exemple :
Extensions
Extension aux graphes
Le nombre de Thue d'un graphe G est le plus petit entier k tel que G possède une k-coloration pour laquelle la suite des couleurs sur tout chemin simple (qui ne passe pas deux fois par le même sommet) est sans carré. Un résultat significatif est que le nombre de Thue d'un graphe planaire est borné[24].
Mot sans carré extrémal
Jarosław Grytczuk, Hubert Kordulewski et Artur Niewiadomski ont introduit la notion de mot sans carré extrémal. Pour cela, ils appellent extension d'un mot tout mot obtenu par insertion d'une lettre dans le mot. Un mot sans carré est extrémal si toute extension de contient un carré. Ainsi, sur l'alphabet à deux lettres , le mot est sans carré extrémal : les 8 extensions , , , , , , , , obtenu par l'insertion d'une lettre contiennent toutes un carré.
Sur un alphabet à trois lettres, le mot
est un mot sans carré extrémal, et c'est le plus court mot ternaire sans carré extrémal[25].
Les auteurs prouvent :
Théorème — Il existe une infinité de mots sans carré extrémaux sur un alphabet à trois lettres.
Il existe des mots sans carré extrémaux pour les longueurs 25, 41, 48, 50, 63, 71, 72, 77, 79, 81, 83, 84, 85 et pour tout entier supérieur ou égal à 87[26].
Une étude et des extensions sont données par Lucas Mol, Narad Rampersad et Jeffrey Shallit[27].
Une question naturelle est de savoir si un analogue du théorème est valable pour des alphabets plus grands. L'étude numérique systématique est compliquée par le fait que si on dispose de quatre lettres, il y a deux possibilités d'extension d'un mot sans carré à chaque position intérieure. En fait, les auteurs[25] n'ont pas trouvé des mots extrémaux sur quatre lettres de longueur au plus 100 et ils conjecturent qu'il n'en existe pas.
Une variante du concept de mot extrémal est la notion de mot « nonchalant » définie par Jarosław Grytczuk, Hubert Kordulewski et Bartłomiej Pawlik et publiée sur arxiv[28]. Un tel mot est produit par une succession d'insertions de lettres dans un mot sans carré tout en conservant le caractère sans carré, en choisissant à chaque étape la dernière occurrence (la plus à droite) qui conserve l'absence de carré. Un exemple est
Le dernier mot est obtenu par l'insertion de la lettre en avant-dernière position. Les auteurs conjecturent qu'une telle séquence nonchalante infinie de mots sans carré existe.
Mot binaire avec peu de carrés
Tout mot binaire assez long contient au moins trois carrés. Plus précisément[29], notent que le mot de longueur 18 contient 2 carrés, et que tout mot binaire lus long en contient au moins trois.
Bien que les carrés soient inévitables sur un alphabet à deux lettres, Entringer, Jackson et Schatz[30] ont prouvé qu'il existe des mots binaires infinis ne contenant aucun carré d'ordre ≥ 3 (L'ordre d'un carré est la longueur de ). La construction d'Entringer, Jackson et Schatz, telle que présentée par Gabric et Shallit[31], est comme suit : on part d'un mot arbitraire sans carré sur l'alphabet {0,1,2} et lui applique le morphisme uniforme
- , , .
Les auteurs prouvent que le mot résultant n'a aucun carré d'ordre ≥ 3 ; en fait, les seuls carrés qui apparaissent sont , , , , et . On peut prendre comme mot de départ le mot de Thue sur 3 lettres .
L'observation de Entringer, Jackson et Schatz a été améliorée par Fraenkel et Simpson[32] : ils ont montré l'existence de mots binaires ayant seulement trois carrés distincts. Leur construction est, d'après Gabric et Shallit[31], difficile à établir.
Pascal Ochem[33] donne, en 2006, une construction différente : il considère le morphisme
et il montre que si est un mot sans puissance d'exposant strictement plus grand que 7/4, alors ne contient que trois carrés.
Harju et Nowotka[34] engendrent un mot binaire infini avec trois carrés en définissant le morphisme (non uniforme)
qu'ils appliquent au mot ternaire de Thue. Ils montrent que le mot obtenu contient seulement trois carrés.
Encore une autre construction a été donnée par Badkobeh et Crochemore[35],[29]. Ils définissent le morphisme
- .
Ils montrent que l'image par du mot de Thue ternaire ne contient que les trois carrés , et . Ils montrent aussi qu'il contient les seuls cubes et .
Une autre construction enfin est donnée par Gabric et Shallit[31]. Ils donnent le morphisme
Ils montrent que le mot infini , où t est le mot de Thue ternaire, ne contient que les carrés 00,11, et 1010. Ils montrent aussi que ce mot est 2-automatique et peut être engendré par un (automate ?) à 27 états.
Mots sans carré en progression arithmétique
Soit
un mot infini, où chaque est une lettre ; on note le mot infini formé en prenant les lettres de en , formellement :
- .
La question suivante a été posée (et résolue ) par Tero Harju[36] : « Pour un entier donné, existe-t-il un mot sans carré sur 3 lettres tel que est aussi sans carré ? » La réponse est positive pour , négative pour . À la fin de son article, Harju pose les questions suivantes : Question 1.- Existe-t-il in mot infini sans carré sur trois lettres tel que les mots pour contiennent tous un carré ?
Question 2.- Existe-t-il deux entiers premiers entre eux tels qu'il existe un mot infini sans carré sur trois lettres pour lequel et sont tous deux sans carrés.
Question 3.- Existe-t-il, pour tout mot sans carré sur trois lettres, un mot sans carré et un entier tel que .
Des réponses affirmatives à ces trois questions ont été données par Currie, Harju, Ochem, et Rampersad[37].
Un problème semblable est étudié par Matthieu Rosenfeld[38] :
Il considère une technique non constructive pour montrer que les carrés sont évitables par un mot infini même si l'on exige que certaines lettres de l'alphabet apparaissent à certaines occurrences. Il montre Nous montrons que si les positions de lettres prédéterminées sont à une distance d'au moins 19 (resp. 3 ou 2) les unes des autres, alors on peut éviter les carrés sur 3 lettres (resp. 4 ou 6 lettres). Le nombre de solutions est exponentiel. Certains calcul ont été faits par ordinateur.
Notes et références
- Thue 1906.
- Thue 1912.
- Marshall Hall Jr., « Generators and relations in groups - The Burnside problem, », dans Lectures on Modern Mathematics, t. II, (MR 0178064), p. 42-92
- C. H. Braunholtz, « An infinite sequence of 3 symbols with no adjacent repeats », American Math. Monthly, vol. 70, , p. 675-676.
- C. E. Arshon, « Démonstration de l'existence de suites asymétriques infinies (en russe avec un long résumé en français) », Mat. Sbornik, vol. 2, no 4, , p. 769-779.
- Marston Morse et Gustav Hedlund, « Unending chess, symbolic dynamics and a problem in semigroups », Duke Math. Journal, vol. 11, , p. 1-7.
- David Hawkins et Walter E. Mientka, « On sequences which contain no repetitions », Math. Student, vol. 24, , p. 185-187.
- C'est la Mathematical Note n° 2726: John Leech, « A problem on strings of beads », The Mathematical Gazette, vol. 41, , p. 277– 278. Un peu plus tard, J. C. Shepherdson, dans : « A Historical Note on Note 2726 », Math. Gazette, vol. 42, no 342, , p. 306 rappelle l'existence des articles de Thue, et que Thue aussi a considéré des mots sans carré bilatères.
- Theodor Zech, « Wiederholungsfreie Folgen », Z. angew. Math. Mech., vol. 38, nos 5/6, , p. 206-209.
- Richard A. Dean, « A sequence without repeats on », American Math. Monthly, vol. 72, , p. 383-385.
- Golnaz Badkobeh, Tero Harju, Pascal Ochem et Matthieu Rosenfeld, « Avoiding square-free words on free groups », Theoretical Computer Science, vol. 922, , p. 206-217 (DOI 10.1016/j.tcs.2022.04.025, arXiv 104.06837).
- Bean, Ehrenfeucht et McNulty 1979.
- Lothaire 1983.
- Thue 1912, Satz 17.
- Crochemore 1982.
- Arturo Carpi, « On the size of a square-free morphism on a three letter alphabet », Information Processing Letters, vol. 16, no 5, , p. 231–235 (ISSN 0020-0190, DOI 10.1016/0020-0190(83)90094-7).
- Wlazinski 2018.
- James Currie et Narad Rampersad, « There are k-uniform cubefree binary morphisms for all k≥0 », Discrete Applied Mathematics, vol. 157, no 11, , p. 2548–2551 (ISSN 0166-218X, DOI 10.1016/j.dam.2009.02.010)
- « Transition Property For Cube-Free Words », déposé sur Arxiv le 28 décembre 2018.
- James D. Currie et Jamie Simpson, « Non-Repetitive Tilings », The Electronic Journal of Combinatorics, vol. 9, no 1, (ISSN 1077-8926, DOI 10.37236/1644).
- Jaroslaw Grytczuk, « Thue-like Sequences and Rainbow Arithmetic Progressions », The Electronic Journal of Combinatorics, vol. 9, no 1, (ISSN 1077-8926, DOI 10.37236/1660).
- Borut Lužar, Martina Mockovčiaková, Pascal Ochem, Alexandre Pinlou et Roman Soták, « On non-repetitive sequences of arithmetic progressions: The cases k∈{4,5,6,7,8} », Discrete Applied Mathematics, vol. 279, , p. 106–117 (DOI 10.1016/j.dam.2019.10.013).
- Arseny M. Shur, « Growth Properties of Power-Free Languages », dans Giancarlo Mauri et Alberto Leporati (éditeurs), Developments in Language Theory - 15th International Conference, DLT 2011, Milan, Italy, July 19-22, 2011. Proceedings, Springer-Verlag, coll. « Lecture Notes in Computer Science » (no 6795), , p. 28-43
- Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak et David Wood, « Planar graphs have bounded nonrepetitive chromatic number », Advances in Combinatorics, (ISSN 2517-5599, DOI 10.19086/aic.12100, arXiv 1904.05269).
- Jarosław Grytczuk, Hubert Kordulewski et Artur Niewiadomski, « Extremal Square-free Words », The Electronic Journal of Combinatorics, vol. 27, no 1, , article no 1.48 (DOI 10.37236/9264, arXiv 1910.06226, lire en ligne, consulté le ).
- Lucas Mol et Narad Rampersad, « Lengths of extremal square-free ternary words », Arxiv, (arXiv abs/2001.11763).
- Lucas Mol, Narad Rampersad et Jeffrey Shallit, « Extremal Overlap-Free and Extremal -Free Binary Words », The Electronic Journal of Combinatorics, vol. 27, no 4, , article no 4.42 (DOI 10.37236/9703, lire en ligne).
- Jarosław Grytczuk, Hubert Kordulewski et Bartłomiej Pawlik, « Square-free extensions of words », arxiv, (arXiv 2104.04841v3).
- Golnaz Badkobeh et Maxime Crochemore, « Fewest repetitions in infinite binary words », RAIRO Inform. Théor. App., vol. 46, , p. 17–31 (lire en ligne, consulté le ).
-
Roger C. Entringer, Douglas E. Jackson et J. A. Schatz, « On nonrepetitive sequences », Journal of Combinatorial Theory, Series A, vol. 16, no 2, , p. 159–164 (DOI 10.1016/0097-3165(74)90041-7)
.
- Gabric et Shallit 2021.
- Aviezri S. Fraenkel et R. Jamie Simpson, « How Many Squares Must a Binary Sequence Contain? », The Electronic Journal of Combinatorics, vol. 2, no 1, (ISSN 1077-8926, DOI 10.37236/1196, lire en ligne).
- Pascal Ochem A generator of morphisms for infinite words, « A generator of morphisms for infinite words », RAIRO Inform. Théor. App., vol. 40, , p. 427–441 (DOI 10.1051/ita:2006020, lire en ligne, consulté le ).
- Tero Harju et Dirk Nowotka. Binary words with few squares, « Binary words with few squares », Bull. European Assoc. Theor. Comput. Sci., no 89, , p. 164–166 (lire en ligne, consulté le ).
- Golnaz Badkobeh, « Infinite words containing the minimal number of repetitions », Journal of Discrete Algorithms, vol. 20, , p. 38–42.
- Tero Harju, « On square-free arithmetic progressions in infinite words », Theoretical Computer Science, vol. 770, , p. 95–100 (DOI 10.1016/j.tcs.2018.09.032).
- James Currie, Tero Harju, Pascal Ochem et Narad Rampersad, « Some further results on squarefree arithmetic progressions in infinite words », Theoretical Computer Science, vol. 799, , p. 140–148 (DOI 10.1016/j.tcs.2019.10.006).
- Matthieu Rosenfeld, « How far away must forced letters be so that squares are still avoidable? », Mathematics of Computation, vol. 89, no 326, , p. 3057–3071 (ISSN 0025-5718, DOI 10.1090/mcom/3535, arXiv 2006.09094)
Bibliographie
Thue
- [Thue (1906)] Axel Thue, « Über unendliche Zeichenreihen », Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, no 7, , p. 1-22.
- [Thue (1912)] Axel Thue, « Über die gegenseitige Lage gleicher Teile gewisser Zeichenreihen », Norske Vid. Skrifter I Mat.-Nat. Kl., Christiania, no 1, , p. 1-67.
- [Thue (1977)] Trygve Nagell, Atle Selberg, S. Selberg et K. Thalberg (éditeurs), Selected Mathematical Papers of Axel Thue, Oslo, Universitetsforlaget, Dans cette collection d’œuvres choisies, l'article de 1906 figure aux pages 139—158, et l'article de 1912 aux pages 413—477.
Lothaire
- M. Lothaire (1983), Combinatorics on words, Addison-Wesley Publishing Co., Reading, Mass., coll. « Encyclopedia of Mathematics and its Applications » (no 17), (ISBN 978-0-201-13516-9, présentation en ligne)
- [Lothaire (1997)] M. Lothaire, Combinatorics on words, Cambridge University Press, coll. « Cambridge Mathematical Library », , 2e éd., xviii+238 (ISBN 978-0-521-59924-5, DOI 10.1017/CBO9780511566097, MR 1475463, présentation en ligne)
Articles
- [Bean, Ehrenfeucht, McNulty (1979)] Dwight R. Bean, Andrzej Ehrenfeucht et George F. McNulty, « Avoidable patterns in strings of symbols », Pacific J. Math., vol. 85, no 2, , p. 261-294 (MR 0574919).
- [Crochemore (1982)] Maxime Crochemore, « Sharp characterizations of squarefree morphisms », Theor. Comput. Sci., vol. 18, no 2, , p. 221-226 (DOI 10.1016/0304-3975(82)90023-8, lire en ligne).
- [Brandenburg (1983)] Franz-Joseph Brandenburg, « Uniformly growing k-th power-free homomorphisms », Theor. Comput. Sci., vol. 23, , p. 69-82.
- [Wlazinski (2018)] Francis Wlazinski, « A uniform cube-free morphism is k-power-free for all integers k ≥ 4 », RAIRO - Theoretical Informatics and Applications, vol. 51, no 4, , p. 205–216 (ISSN 0988-3754, DOI 10.1051/ita/2017015, HAL hal-01417750)
- [Gabric Shallit (2021)] Daniel Gabric et Jeffrey Shallit, « The simplest binary word with only three squares », RAIRO - Theoretical Informatics and Applications, vol. 55, no 3, (ISSN 0988-3754, DOI 10.1051/ita/2021001, arXiv 2007.08188)
Voir aussi
- Perles de Dijkstra
- La suite de Prouhet-Thue-Morse est sans facteur cubique.
- La suite de Fibonacci est sans facteur biquadratique.
Liens externes
- (en) Eric W. Weisstein, « Squarefree Word », sur MathWorld