La conjecture de Billaud est une conjecture en combinatoire des mots, formulée par Michel Billaud, qui concerne une propriété qu'un mot vérifie s'il en est ainsi pour ses sous-mots obtenus en effaçant toutes les occurrences d'une lettre.

La conjecture de Billaud est la suivante :

La conjecture a été formulée en 1993^[1] et est encore ouverte en 2022.

La conjecture est trivialement vérifiée pour un alphabet à 2 lettres, et a été démontrée par P. Zimmermann « A problem with words from Michel Billaud » pour un alphabet à 3 trois lettres^[2]. Françoise Levé et Gwénaël Richomme ont démontré^[2] la conjecture dans le cas où chaque morphisme ${\displaystyle f_{x}}$ de l'énoncé n'a qu'une seule lettre expansive (une lettre ${\displaystyle a}$ est dite expansive pour un morphisme ${\displaystyle h}$ si ${\displaystyle a}$ figure dans l'image ${\displaystyle h(a)}$ et si ${\displaystyle h(a)}$ est de longueur au moins 2). La conjecture a été prouvée pour un alphabet à 4 lettres^[3].

On considère^[2] le morphisme ${\displaystyle f}$ sur ${\displaystyle \{1,2,3,4,5,6,7,8,9\}}$ donné par

${\displaystyle f(1)=2}$, ${\displaystyle f(2)=1}$, ${\displaystyle f(3)=34}$, ${\displaystyle f(4)=435}$, ${\displaystyle f(5)=6}$, ${\displaystyle f(6)=7}$, ${\displaystyle f(7)=\varepsilon }$, ${\displaystyle f(8)=6787}$, ${\displaystyle f(9)=966}$.

Les lettres mortelles sont ${\displaystyle \{5,6,7\}}$, les lettres expansives sont ${\displaystyle \{8,9\}}$. Les points fixes de ${\displaystyle f}$ sont les mots de ${\displaystyle \{76787,96677\}^{*}}$ puisque en effet par exemple

${\displaystyle f(76787)=\varepsilon \cdot 7\cdot \varepsilon \cdot 6787\cdot \varepsilon }$.

On note FW l'ensemble des mots qui sont points fixes d'un morphisme non trivial

${\displaystyle \mathrm {FW} =\{w\mid \exists f\neq \mathrm {Id} :f(w)=w\}}$.

Un témoin pour un mot ${\displaystyle w}$ dans FW est un morphisme ${\displaystyle f}$ non trivial tel que ${\displaystyle f(w)=w}$. Enfin, on note ${\displaystyle \delta _{x}(w)}$ le mot obtenu en effaçant toutes les occurrences de la lettre ${\displaystyle x}$ dans ${\displaystyle w}$. Un tel mot est un héritier (heir en anglais) de ${\displaystyle w}$.

.

Un mot est morphiquement primitif^[4] s'il n'a pas d'autres points fixes que le morphisme identité. Par définition, un mot est morphiquement primitif si et seulement s'il n'appartient pas à l'ensemble FW. La conjecture de Billaud, par contraposition, s'énonce comme suit^[5] :

Tester si un mot est morphiquement primitif peut se faire en temps linéaire^[6]. La conjecture de Billaud est une implication et non une caractérisation. Ainsi, alors qu'il existe des mots morphiquement non primitifs, tels que le mot ${\displaystyle ababcdcd}$ (point fixe du morphisme ${\displaystyle a\mapsto ab}$,${\displaystyle b,d\mapsto \varepsilon }$, ${\displaystyle c\mapsto cd}$), dont aucun des héritiers ${\displaystyle ababcc}$, ${\displaystyle ababdd}$, ${\displaystyle aacdcd}$ et ${\displaystyle bbcdcd}$ n'est morphiquement primitif, il existe également des mots tels que ${\displaystyle abccbcca}$, qui sont morphiquement imprimitifs, mais dont certains héritiers sont morphiquement primitifs (ici ${\displaystyle abba}$ et ${\displaystyle acccca}$).

Michel Billaud est, de 1984 à 2021, Maître de Conférences au Département Informatique de l'Institut Universitaire de Technologie de l'Université Bordeaux ; il est membre du Laboratoire Bordelais d'Informatique (LaBRI)^[7]

• M. Billaud, « A problem with words », Letter in Newsgroup Comp. theory,‎ 1993 (lire en ligne)
• Françoise Levé et Gwénaël Richomme, « On a conjecture about finite fixed points of morphisms », Theoretical Computer Science, vol. 339, n^o 1,‎ juin 2005, p. 103–128 (DOI 10.1016/j.tcs.2005.01.011 , lire en ligne)
• Daniel Reidenbach et Johannes C. Schneider, « Morphically primitive words », Theoretical Computer Science, vol. 410, n^o 21,‎ 17 mai 2009, p. 2148–2161 (DOI 10.1016/j.tcs.2009.01.020 , lire en ligne)
• Szymon Łopaciuk et Daniel Reidenbach, « On Billaud words and their companions », Theoretical Computer Science, vol. 940,‎ 9 janvier 2023, p. 231–253 (DOI 10.1016/j.tcs.2022.11.004 , lire en ligne)

• Szymon Łopaciuk et Daniel Reidenbach, « The Billaud Conjecture for ${\displaystyle \Sigma =4}$, and Beyond », Lecture Notes in Computer Science, Springer International Publishing, vol. 13257 « Developments in Language Theory »,‎ 2022, p. 213–225 (ISBN 978-3-031-05578-2, DOI 10.1007/978-3-031-05578-2_17, lire en ligne)

• Portail de l'informatique théorique
• Arithmétique et théorie des nombres