Utilisateur:ManiacParisien/Brouillons/Bio-4

En combinatoire, et plus particulièrement en combinatoire des mots, un mot privilégié (en anglais privileged word) est un mot qui possède un bord d'une forme particulière. Les mots privilégiés sont des cas particuliers des mots de retour (aussi appelés mots fermés) et permettent des caractérisations remarquables de certains mots infinis.

Définitions

Un mot de retour complet (aussi appelé mot fermé) est un mot qui possède un bord (non vide) qui apparaît exactement deux fois. Ce bord est alors unique. Formellement, un mot de retour complet $w$ est un mot dans $uA^{*}\cap A^{*}u\setminus A^{+}uA^{+}$. Dans cette expression, $u$ est bord en question ; on dit que $w$ est un mot de retour complet pour $u$. Ce mot $u$ est parfois appelée la frontière de $w$.

La définition des mots privilégiés est par récurrence :

• Le mot vide et toute lettre est un mot privilégié ;
• Un mot $w$ de longueur au moins 2 est privilégié s'il possède un bord privilégié (non vide) qui apparaît exactement deux fois dans $w$.

Le mot vide apparaît au moins 3 fois dans un mot de longueur au moins 2, donc est exclu dans la deuxième partie de la définition. Un bord qui apparaît exactement deux fois est unique, c'est le plus grand bord ou frontière. Un mot sans bord n'est pas privilégié sauf s'il est de longueur 0 ou 1.

Un mot privilégié est donc un mot complet de retour dont la frontière est elle-même privilégié. Une discussion soignée est donnée par Gabriele Fici.

Exemples

Sur l'alphabet $a,b$, les mots suivants sont privilégiés :

$\varepsilon ,a,b,aa,bb,aaa,aba,bab,bbb$

mais $abab$, qui est bien un mot de retour complet, n'est pas privilégié parce que le bord $ab$ n'est pas un mot privilégié.

Le nombre de mots binaires privilégié est donné par la suite A231208 de l'OEIS ; la suite commence par :

1, 2, 2, 4, 4, 8, 8, 16, 20, 40, 60, 108, 176, 328, ...

Les 8 mots binaires privilégiés de longueur 5 sont :

00000,00100,01010,01110,10001,10101,11011,11111

Le plus court mot privilégié binaire qui n'est pas un palindrome est 00101100, de longueur 8.

Propriétés

Tout bord d'un mot mot privilégié est lui-même un mot privilégié.

Ainsi le mot $aaa$ est privilégié parce que le bord $aa$ n'apparaît que deux fois ; la lettre $a$ est aussi privilégiée, même si elle apparaît trois fois dans $aaa$.

Tout mot de longueur $n$ possède exactement $1+n$ facteurs privilégiés distincts.

Exemple : le mot $aaabaaab$ de longueur 8 possède 9 facteurs privilégiés. En fait, chaque préfixe de ce mot se termine par un facteur privilégié. Dans la table, le suffixe privilégié de chaque préfixe est souligné.

préfixe	privilégié
$\varepsilon$	$\varepsilon$
${\underline {a}}$	$a$
${\underline {aa}}$	$aa$
${\underline {aaa}}$	$aaa$
$aaa{\underline {b}}$	$b$
$aa{\underline {aba}}$	$aba$
$a{\underline {aabaa}}$	$aabaa$
${\underline {aaabaaa}}$	$aaabaaa$
$aaa{\underline {baaab}}$	$baaab$

Pour les facteurs fermés, le résultat correspondant est :

Tout mot de longueur $n$ possède au moins $1+n$ facteurs fermés distincts.

Estimation asymptotique

Le nombre binaire de mots privilégiés double pratiquement à chaque étape. Forsyth et.al. ont montré qu'il existe au moins $2^{n-5}/n^{2}$ mots privilégiés binaires de longueur $n$, estimation améliorée en $cq^{n}/n(\log _{q}n)^{2}$ sur un alphabet à $q$ lettres et pour une constante $c$ par Nicholson et Rampersad.

Langages des mots fermés ou privilégiés

L'ensemble des mots privilégiés et l'ensemble des mots fermés sont, ni l'un ni l'autre, des langages algébriques dès que l'alphabet a au moins deux lettres.

Suites caractéristiques

Pour un mot infini $x$ donné, on considère une certaine propriété $P$ des préfixes de $x$ ; pour cela, on regarde la suite des longueurs des préfixes de $x$ vérifiant cette propriété, et on lui associe la suite caractéristique $\chi _{P}(x)$ ; par définition, $\chi _{P}(x)(i)=1$ si le préfixe de longueur $i$ de $x$ vérifie la propriété, et est égal à 0 sinon. Par exemple, pour le mot de Fibonacci

$F=abaababaabaaba\cdots$

si on regarde les positions où se termine un carré, on obtient la suite

$\chi =00010101111111\cdots$,

et si on regarde les positions où se termine un préfixe carré, on obtient la suite

$\chi =00000100010000\cdots$.

La suite caractéristique des préfixes fermés du mot de Fibonacci est :

$\chi =10101100111000111110\cdots$.

Ici les blocs de 1 consécutifs (comme ceux de 0 consécutifs) ont des longueurs qui sont les nombres de Fibonacci...

Bibliographie

• [2018] Jeremy Nicholson et Narad Rampersad, « Improved estimates for the number of privileged words », Arxiv,‎ 31 janvier 2018 (arXiv 1506.07847v2).
• [2013] Jarkko Peltomäki, « Introducing privileged words: Privileged complexity of Sturmian words », Theoret. Comput. Sci., vol. 500,‎ 2013, p. 57–67.
• [2015] Jarkko Peltomäki, « Privileged Factors in the Thue-Morse Word - A Comparison of Privileged Words and Palindromes », Discrete Applied Mathematics 193 (2015), 187--199, vol. 193,‎ 2015, p. 187-199 (DOI 10.1016/j.dam.2015.04.027, arXiv 1306.6768v2).
• [2013] Johannes Kellendonk, Daniel Lenz et Jean Savinien, « A characterization of subshifts with bounded powers », Discrete Math, vol. 313,‎ 2013, p. 2881–2894 (arXiv 1111.1609).
• [2016] M. Forsyth, A. Jayakumar, Jarkko Peltomäki et J. Shallit, « Remarks on privileged words », Int. J. Found. Comput. Sci., vol. 27,‎ 2016, p. 431–442 (arXiv 1311.7403).
• [2017] Gabriele Fici, « Open and Closed Words », Bulletin of EATCS, n^o 123,‎ octobre 2017 (lire en ligne).
• [2016] Jarkko Peltomäki, Privileged Words and Sturmian Words (Thèse), University of Turku, coll. « Doctoral dissertation (monograph) », 174 p. (ISBN 978-952-12-3421-7, lire en ligne).