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 A un alphabet, et soit E un autre alphabet, appelé l'alphabet des symboles de motifs ou des variables. Un motif est un mot non vide sur E. Un mot v sur A est une instance d'un motif p s'il existe un morphisme non effaçant f: E^+ \to A^+ tel que f( p ) =v. Un mot w évite le motif p si aucun facteur v de w n'est une instance de p. Une définition équivalente est la suivante : le langage du motif p est l'ensemble des mots f(p), où f est comme ci-dessus un morphisme non effaçant; un mot w évite le motif p si aucun facteur de w est dans le langage de p. Si w n'évite pas le motif p, on dit que w rencontre p ou contient une instance du motif p[1].

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

Un motif p est évitable s'il existe une infinité de mots sur un alphabet fini que évitent p. De manière équivalente, un motif est évitable s'il existe un mot infini qui évite p. Dans le cas contraire, le motif p est dit inévitable[2]. Par exemple, le motif xyx 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]

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

S'il existe un mot infini sur k lettres qui évite un motif p, le motif est dit k-évitable. Sinon, il est k-inévitable. Si p est évitable, le plus petit entier k tel que p est k-évitable est appelé l'indice d'évitabilité de p[7]. Si p est inévitable, son indice d'évitabilité est, par définition, \infty. Par exemple, comme le motif xyx est inévitable, son indice est \infty. En revanche, l'indice d'évitabilité du motif xx 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 x et y, on a[8] :

  • 1,x,xy,xyx sont inévitables;
  • xx,xxy,xyy,xxyx,xxyy,xyxx,xyxy,xyyx,xxyxx,xxyxy,xyxyy ont l'indice d'évitabilité 3;
  • tous les autres motifs ont 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]