Accueil🇫🇷Chercher

Sesquipuissance

En mathématiques, en informatique théorique, et notamment en combinatoire des mots, une sesquipuissance ou mot de Zimin[1] est un mot sur un alphabet qui possède un préfixe propre qui est aussi un suffixe propre. En d'autre termes, une sesquipuissance est un mot avec bord. Une sesquipuissance est un motif inévitable, en ce sens que tout mot assez long en contient une en facteur. On définit par récurrence des sesquipuissances d'ordre n>1 : ce sont des mots qui ont un bord qui lui-même est une sesquipuissances d'ordre n-1.

Suite bi-idéale

Soit un alphabet. On définit sur les sesquipuissances d'ordre , par récurrences sur comme suit. Tout mot non vide sur est une sesquipuissance d'ordre ; si est une sesquipuissance d'ordre et est un mot non vide, alors est une sesquipuissance d'ordre [2]. Le degré d'un mot non vide est le plus grand entier tel que est une sesquipuissance d'ordre [3].

Une suite bi-idéale est une suite de mots , avec un mot non vide, et tel que, pour , il existe un mot non vide avec

.

Avec cette définition, le degré d'un mot est la longueur de la plus longue suite bi-idéale se terminant par [3].

Pour un alphabet fini à lettres, il existe un entier dépendant de et de tel que tout mot de longueur possède un facteur qui est une sesquipuissance d'ordre au moins . Ceci signifie que les sesquipuissances sont des motifs inévitables[4] - [5].

Dans toute suite bi-idéale , le mot est un préfixe propre de , et la suite converge vers le mot infini

Un mot infini est une sesquipuissance s'il est la limite d'une suite bi-idéale infinie[6]. Un mot infini est une suite bi-idéale si et seulement s'il est un mot récurrent[6] - [7], c'est-à-dire si tous ses facteurs apparaissent infiniment souvent[8].

Supposons fixé un ordre total sur les lettres de l’alphabet . Pour des entiers positifs quelconques et , tout mot assez long ou bien possède un facteur qui est une puissance d'ordre , ou un facteur qui est une sesquipuissance d'ordre au moins ; dans le deuxième cas, ce facteur a une factorisation en mots de Lyndon[7].

Mot de Zimin

Les mots de Zimin sont les éléments d'une suite bi-idéale particulière, où le facteur central de chaque terme est une nouvelle lettre : ils sont définis par récurrence par :

,

où sont des letres.

  • Les mots de Zimin d'ordre 1,2,... les plus courts sont :
a, aba, abacaba, abacabadabacaba
Ici, a, b, c, d sont des lettres. Leurs longueurs forment la suite A123121 de l'OEIS. Ces mots interviennent dans la description des mouvements du jeux des tours de Hanoï.
  • Les exposants des plus hautes puissances de 2 qui divisent les entiers naturels positifs sont :
0102010301020104010201030102010...
Les préfixes de longueur sont des mots de Zimin.
  • Les mots de Zimin forment des motifs inévitables, en ce sens que tout mot assez long en contient une en facteur.

Bornes sur les mots de Zimin

Les bornes sur la longueur des mots de Zimin continuent à être un sujet d'étude actif.

Notes et références

  1. Dénommé ainsi d'après son inventeur, le mathématicien russe A. Zimin.
  2. de Luca et Varricchio 2011, p. 135
  3. de Luca et Varricchio 2011, p. 136
  4. de Luca et Varricchio 2011, p. 137
  5. Berstel et al. 2008, p. 132
  6. de Luca et Varricchio 2011, p. 141
  7. Berstel et al. 2008, p. 133
  8. Berstel et Perrin 2011, p. 30
(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sesquipower » (voir la liste des auteurs).

Bibliographie

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.