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 sesquipuissances sont inévitables[5].

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 [7]. 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[8] :

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

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. Cassaigne 2011, p. 124.
  8. Cassaigne 2011, p. 126.

(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]