Utilisateur:Vers75/Brouillon1

En combinatoire, et particulièrement en combinatoire des mots un mot fermé est un mot qui commence et fini par un mot $u$ sans contenir d'autres occurrences de $u$. Un mot de fermé est aussi appelé un mot de retour complet.

Ces mots permettent de séparer deux occurrences consécutives d'un facteur dans un mot infini, et ainsi de découper des mots infinis en un produit de facteurs finis, et leur nombre et leurs occurrences permettent de caractériser des familles de mots infinis comme les mots sturmiens.

Définition et exemples

Un mot $x$ est fermé s'il est constitué d'au plus une lettre, ou s'il possède un bord (un préfixe et suffixe tous deux non vides) qui apparaît exactement deux fois dans $x$ , formellement s'il appartient à l'ensemble $uA^{*}\cap A^{*}u\setminus A^{+}uA^{+}$, pour un mot $u$ et où $A$ est l'alphabet. Les premiers mots fermés sur un alphabet binaire sont

$\varepsilon ,a,b,aa,bb,aaa,aba,bab,bbb,aaaa,abab,abba,baab,baba,bbbb$.

Le plus long bord d'un mot fermé est appelé sa frontière. Par exemple, le mot $aabaa$ est fermé, sa frontière est le mot $aa$. Un mot est ouvert s'il n'est pas fermé. Le mot $aabab$ est ouvert, car il est sans bord. Le mot $aabaaa$ aussi est ouvert : sa frontière est $aa$, mais elle apparaît trois fois dans ce mot.

Un mot $x$ est un mot de retour complet pour un mot $u$ s'il commence par $u$, se termine par $u$ et ne contient pas $u$ en facteur interne, formellement s'il appartient à l'ensemble $uA^{*}\cap A^{*}u\setminus A^{+}uA^{+}$, où $A$ est l'alphabet. Ainsi, $x$ est un mot de retour complet pour un mot $u$ si $x$ est fermé et sa frontière est $u$. Un mot réduit à une lettre est un mot de retour complet. Un mot de retour (sans la spécification « complet ») pour un mot $u$ est un mot $y$ tel que $yu$ est un mot de retour complet pour $u$. Par exemple, $y=ab$ est un mot de retour pour $u=aba$ puisque $x=ababa$est un mot de retour complet. Un mot de retour pour $u$ est donc $u$ en préfixe ou est un préfixe de $u$.

Soit $w$ un mot infini et soit $u$ un préfixe de $w$. On considère l'ensemble $S(u)$ des débuts d'occurrence de $u$ dans $w$. Si $s<t$ sont deux éléments consécutifs de $S(u)$, alors le facteur $w[s,t-1]$ de $w$ qui commence en position $s$ et se termine en position $t-1$ est un mot de retour.

Exemple 1 : mot de Champernowne

Soit ${\underline {01}}00{\underline {01}}1{\underline {01}}10000{\underline {01}}{\underline {01}}0{\underline {01}}1\ldots$ le mot de Champernowne binaire formé de la concaténation des développements binaires des entiers naturels. Les débuts d'occurrences du facteur $u=01$ sont en position $0,4,7,13,15,\ldots$, et le mot de Champernowne est le produit des mots de retour commençant en ces positions, soit $0100\cdot 011\cdot 0110000\cdot 01\cdot 010\cdot 011\ldots$. Comme le mot est récurrent (tout facteur du mot apparaît une infinité de fois dans le mot), cette factorisation du mot de Champernowne en un produit infini de facteurs fini est possible.

Exemple 2 : Mot de Fibonacci

Le mot de Fibonacci $010010100100101001010\ldots$ est uniformément récurrent. Par exemple, les occurrences du chiffre $1$ dans ce mot infini sont les éléments de la suite A001950 de l'OEIS, soit 1, 4, 6, 9, 12, 14, 17,... en commençant la numérotation à 0. La distance entre deux $1$ consécutifs est donc au plus 3.

Le préfixe 010 apparaît aux positions 0, 3, 5, 8,..., et le mot se factorise en $010\cdot 01\cdot 010\cdot 010\cdot 01\cdot 010\cdot 01\cdot 010\ldots$. Les mots de retour pour $010$ dans le mot de Fibonacci sont au nombre de deux : ce sont $01$ et $010$.

Les mots de retour pour un préfixe d'un mot infini sont en nombre fini seulement si ce préfixe apparaît à distance bornée, ce qui est le cas lorsque le mot infini est uniformément récurrent. Les mots de retour sont des mots finis seulement si ce préfixe apparaît une infinité de fois, ce qui est le cas lorsque le mot est récurrent.

Mots de retour des mots sturmiens

Les mots sturmiens sont caractérisés comme suit par leurs mots de retour :

• Dans tout mot sturmien, tout préfixe possède exactement deux mots de retour. Il est équivalent de dire que la distance entre deux occurrences consécutives d'un préfixe d'un mot sturmien prend exactement deux valeurs.
• Réciproquement, si tout préfixe d'un mot infini possède exactement deux mots de retour, alors ce mot est sturmien.

On peut aussi voir cette propriété comme suit : un mot sturmien s'écrit comme un produit infini de deux facteurs fini. En renommant ces facteurs, le produit de ces symboles est un mot infini qui est à nouveau sturmien, sur ce nouvel alphabet.

On peut caractériser les mots points fixes de morphismes par leurs mots de retour.

Complexité ouverte et fermée

La complexité fermée d'un mot $x$ (fini ou infini) est la fonction qui, à chaque entier $n$, associe le nombre $Cl_{x}(n)$ de facteurs fermés de longueur $n$ dans $x$. De même, la complexité ouverte associe à chaque entier $n$, associe le nombre $Op_{x}(n)$ de facteurs ouverts de longueur $n$ dans $x$.

Par exemple, le mot $x=(abba)^{\omega }$ a deux facteurs fermés de longueur 2, à savoir $aa$ et $bb$, et donc $Cl_{x}(2)=2$ pour ce mot. Aucun de ses facteurs de longueur 3 n'est fermé, donc $Cl_{x}(3)=0$. Tout facteur est soit ouvert soit fermé, donc on a

$Cl_{x}(n)+Op_{x}(n)=c_{x}(n)$

où $c_{x}(n)$ est le nombre de facteurs de longueur $n$. On a le résultat suivant :

Théorème (Parshina, Postic) — Pour un mot infini $x$, les trois conditions sont équivalentes :

1. $x$ est apériodique
2. $\liminf Cl_{x}(n)=+\infty$
3. $\limsup Op_{x}(n)=+\infty$.

Chacune des conditions 2 ou 3 implique que le mot est apériodique, car un mot périodique n'a qu'un nombre fini de facteurs (et donc de facteurs fermés ou ouverts) de chaque longueur.

La table des plus long facteurs fermés

Le table des plus long facteurs fermés (the longest closed factor array) d'un mot $w$ de longueur $n$ est le vecteur $LC_{w}[1..n]$ tel que, pour $1\leq i\leq n$, $LC_{w}[i]$ est la longueur du plus long facteur fermé de $w$ commençant en position $i$.

Par exemple, pour $w=abcaacab$, on a $LC_{w}=[8,7,5,2,3,1,1,1]$.

La table des plus long facteurs fermés d'un mot de longueur $n$ peut être calculée en tembs $O(n{\sqrt {\log n}})$.

Graphe de Rauzy

En combinatoire, et particulièrement en combinatoire des mots, le graphe de Rauzy est un graphe qui décrit l'évolution du cheminement dans un mot fini ou infoni. Il a été introduit par Gérard Rauzy. le graphe de Rauzy d'ordre $n$ d'un mot $x$ est le graphe orienté dont les sommets sont les facteurs de longueur n du mot $x$ et dont les arcs sont étiquetés par les facteurs de longueur $n+1$ ; il y a un arc étiqueté $w$ du sommet $s$ vers le sommet $t$ si $s$ est préfixe et $t$ est suffixe de $w$. En d'autres termes, le mot $w$ s'écrit $w=sa=bt$ pour deux lettres $a$ et $b$. Le graphe de de Bruijn est le graphe de Rauzy particulier correspondant à un mot de de Bruijn.

Bibliographie

• Golnaz Badkobeh, Alessandro De Luca, Gabriele Fici et Simon J. Puglisi, « Maximal Closed Substrings », Lecture Notes in Computer Science, Springer « String Processing and Information Retrieval (SPIRE) »,‎ 2022, p. 16–23 (ISBN 978-3-031-20643-6, DOI 10.1007/978-3-031-20643-6_2, lire en ligne, consulté le 10 janvier 2024)

• Hideo Bannai, Shunsuke Inenaga, Tomasz Kociumaka, Arnaud Lefebvre, Jakub Radoszewski, Wojciech Rytter, Shiho Sugimoto et Tomasz Walen, « Efficient Algorithms for Longest Closed Factor Array », Lecture Notes in Computer Science, Springer, vol. 9309 « String Processing and Information Retrieval »,‎ 2015, p. 95–102 (ISBN 978-3-319-23826-5, DOI 10.1007/978-3-319-23826-5_10, lire en ligne, consulté le 11 janvier 2024)

• Olga Parshina et Svetlana Puzynina, « Finite and infinite closed-rich words », Theoretical Computer Science, vol. 984,‎ 12 février 2024, article n^o 114315, 12 p. (DOI 10.1016/j.tcs.2023.114315, arXiv 2111.00863)

• Julien Cassaigne, Gabriele Fici, Marinella Sciortino et Luca Q. Zamboni, « Cyclic Complexity of Words », Journal of Combinatorial Theory, Series A, vol. 145,‎ 2017, p. 36-56 (DOI 10.1016/j.jcta.2016.07.002, arXiv 1402.5843, lire en ligne, consulté le 3 mars 2021).

• Fabien Durand, « A characterization of substitutive sequences using return words », Discrete Math., vol. 179,‎ 1998, p. 89-101.

• Gabriele Fici, « Open and closed words », Bulletin of the European Association for Theoretical Computer Science, n^o 123,‎ 2017, p. 140-149 (lire en ligne, consulté le 3 mars 2021).

• Olga Parshina et Mickaël Postic, « Open and closed complexity of infinite words », submitted,‎ 2020 (arXiv 2005.06254).

• Luke Schaeffer et Jeffrey Shallit, « Closed, rich, privileged, trapezoidal, and balanced words in automatic sequences », The Electronic Journal of Combinatorics, vol. 23, n^o 1,‎ 2016, article n^o P1.25 (lire en ligne, consulté le 3 mars 2021)
• Laurent Vuillon, « A characterization of sturmian words by return words », European Journal of Combinatorics, vol. 22, n^o 2,‎ 2001, p. 263–275 (DOI 10.1006/eujc.2000.0444).