Motif inévitable

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

En informatique théorique, en combinatoire, et notamment en combinatoire des mots, un motif inévitable est un motif (au sens défini ci-dessous) qui apparaît dans tout mot assez long. Un motif est évitable sinon. Par exemple, le motif xx est inévitable sur deux lettres et inévitable sur trois lettres, parce que tout mot assez long sur deux lettres contient un carré (composé de deux facteurs consécutifs égaux), et qu'il existe des mots arbitrairement longs sans carré sur trois lettres.

Les motifs évitables et inévitables généralisent la notion de répétition dans les mots, et leur étude s'inscrit dans celle des régularités dans les mots.

Définitions[modifier | modifier le code]

Soit un alphabet, et soit un autre alphabet, appelé l'alphabet des symboles de motifs ou des variables. Un motif est un mot non vide sur E. Un mot sur est une instance d'un motif s'il existe un morphisme non effaçant tel que . Un mot évite le motif si aucun facteur de n'est une instance de . Une définition équivalente est la suivante : le langage du motif est l'ensemble des mots , où est comme ci-dessus un morphisme non effaçant; un mot évite le motif si aucun facteur de est dans le langage de . Si n'évite pas le motif , on dit que rencontre ou contient une instance du motif [1].

Par exemple, le mot (où sont des lettres de ) rencontre le motif ( et sont des lettres de ); en effet, le facteur de est l'image de par le morphisme qui envoie sur et sur . Le facteur aussi est dans le langage du motif  : il est l'image de par le morphisme qui envoie sur et sur . Le mot évite le motif , puisqu'il ne contient pas de carré, c'est-à-dire pas deux facteurs consécutifs égaux[2].

Un motif est évitable s'il existe une infinité de mots sur un alphabet fini qui évitent . De manière équivalente, un motif est évitable s'il existe un mot infini qui évite . Dans le cas contraire, le motif est dit inévitable[2]. Par exemple, le motif est inévitable : tout mot assez long contient deux occurrences de la même lettre séparées par au moins une lettre.

Exemples[modifier | modifier le code]

  • La suite de Prouhet-Thue-Morse évite les motifs (elle est sans cube) et (elle est sans facteur chevauchant)[3],[2].
  • Les motifs et sont inévitables sur tout alphabet[4],[5].
  • Le motif est évitable sur trois lettres[3],[4]. Les mots qui évitent ce motif sont appelés mots sans carré[6],[2].
  • Les motifs pour sont évitables sur deux lettres : la suite de Prouhet-Thue-Morse est un exemple pour [3].
  • Les mots de Zimin (ou sesquipuissances) sont inévitables[5].
  • Tout mot de longueur au moins 29 sur 3 lettres contient un occurrence du motif

Le motif ABACABA[modifier | modifier le code]

Ce motif est le point de départ d'études ou de recherches sur des objets auto-similaires, et donné lieu à plusieurs publications scientifiques ou plus ludiques[7], notamment

Indice d'évitabilité[modifier | modifier le code]

S'il existe un mot infini sur lettres qui évite un motif , le motif est dit -évitable. Sinon, il est -inévitable. Si est évitable, le plus petit entier tel que est -évitable est appelé l'indice d'évitabilité de [8]. Si est inévitable, son indice d'évitabilité est, par définition, . Par exemple, comme le motif est inévitable, son indice est . En revanche, l'indice d'évitabilité du motif est 3, car il existe un mot sans carré infini sur trois lettres, et il n'en existe pas sur deux lettres.

Pour les motifs binaires, sur deux variables et , on a[9] :

  • sont inévitables;
  • les motifs ont l'indice d'évitabilité 3;
  • tous les autres motifs ont l'indice d'évitabilité 2.

Bornes sur les mots de Zimin[modifier | modifier le code]

Les mots de Zimin sont définis par récurrence par

et ,

sont des lettres. Les premiers mots sont :

On s'intéresse à la longueur des mots sur un alphabet à lettres qui contient en facteur une copie du mot de Zimin , c'est-à-dire une image du mot , où chaque lettre est remplacée par un mot non vide. Ainsi, le mot

est une copie de , de même est une copie de (en remplace au choix par et par , ou on laisse inchangé et on remplace par ). Plus généralement, contient deux copies de , et est une copie de obtenue en remplaçant les occurrences de la première lettre par .

On définit une fonction par :

est le plus petit entier tel que tout mot de longueur sur un alphabet à lettres contient en facteur une copie du mot de Zimin .

On a et . La deuxième égalité vient du fait que, par le principe du tiroir, au moins une lettre apparaît trois fois dans tout mot de longueur . La copie de consiste en la première et la troisième occurrence de cette lettre, le facteur non vide qui les sépare étant l'image de la lettre . D'autre part, la borne est atteinte puisque le mot de longueur ne contient pas de copie de .

Une relation de récurrences sur est donnée par la formule suivante de Cooper et Rorabaugh[10] :

.

Un mot de longueur se factorise en effet en mots, chacun de longueur séparés par une lettre. Chacun des facteurs de longueur contient une copie de . Comme il y en a , deux de ces facteurs sont égaux. Comme ces deux copies sont séparées par au moins une lettre, ceci fournit une copie de . On peut améliorer cette majoration dans le cas de 3 lettres[11] :

En fait, on a même[12] :

.

Des majorations et minorations pour d'autres cas font intervenir une fonction tour (tower en anglais) d'itération d'exponentiation, notée et définie par :

et .

Ainsi

, , , .

Avec ces notations, on a:

et aussi une minoration sous forme d'une tour d'exponentielles, même dans le cas d'un alphabet binaire[12],[13] :

et (pour ).

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

  1. Cassaigne 2011, p. 112
  2. a, b, c et d Berstel et al. 2008, p. 127
  3. a, b et c Cassaigne 2011, p. 113.
  4. a et b Allouche et Shallit 2003, p. 24.
  5. a et b Cassaigne 2011, p. 115.
  6. Cassaigne 2011, p. 114.
  7. En plus, ce sigle est également un nom commercial.
  8. Cassaigne 2011, p. 124.
  9. Cassaigne 2011, p. 126.
  10. Cooper et Rorabaugh 2014.
  11. Rytter et Shur 2015.
  12. a et b Conlon, Fox et Sudakov 2017.
  13. Carayol et Göller 2017.

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Unavoidable pattern » (voir la liste des auteurs).

Bibliographie[modifier | modifier le code]

Chapitres dans des livres
Articles
  • [2014] Joshua Cooper et Danny Rorabaugh, « Bounds on Zimin word avoidance », Congressus numerantium, vol. 222,‎ , p. 87-95 (ISSN 0384-9864, Math Reviews 3328869).
  • [2015] Wojciech Rytter et Arseny M. Shur, « Searching Zimin patterns », Theoret. Comput. ci., vol. 571,‎ , p. 50-57 (DOI 10.1016/j.tcs.2015.01.004).
  • [2016] Joshua Cooper et Danny Rorabaugh, « Asymptotic density of Zimin words », Discrete Math. Theor. Comput. Sci., vol. 18, no 3,‎ , article no 3 (25 pages) (Math Reviews 3625459).
  • [2017] David Conlon, Jacob Fox et Benny Sudakov, « Tower-type bounds for unavoidable patterns in words », préprint (arxiv),‎ (arXiv 1704.03479).
  • [2017] Arnaud Carayol et Stefan Göller, « On Long Words Avoiding Zimin Patterns », dans Heribert Vollmer et Brigitte Vallée (éditeurs), 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017), coll. « Leibniz International Proceedings in Informatics (LIPIcs) » (no 66), (ISBN 978-3-95977-028-6, ISSN 1868-8969, DOI 10.4230/LIPIcs.STACS.2017.19, lire en ligne), p. 19:1-19:13.