Conclusion

Nous avons au cours de cette thèse abordé un certain nombre d'aspects de la théorie des motifs évitables, dans lesquels il est apparu que les L-systèmes tiennent une place privilégiée. D'autres aspects non moins intéressants ont été laissés de côté, par exemple les propriétés topologiques de l'ensemble des mots qui évitent un motif donné, actuellement étudiées par James Currie (voir aussi [5,57,58,59]), la recherche d'algorithmes efficaces pour tester si un mot contient un motif [44, 45, 46], ou encore l'étude des mots maximaux évitant un motif inévitable donné.

Pour finir, voici quelques questions que nous jugeons intéressantes (certaines de ces questions figurent aussi dans [4,5,17], avec plusieurs autres).

Nous pensons que la conjecture suivante est vraie :
Conjecture : Tout motif k-évitable est k-HDOL-évitable.
Comme on l'a vu page 101, elle pourrait permettre de démontrer la décidabilité de la k-évitabilité. Une voie possible pour attaquer cette conjecture serait de montrer d'une part que pour tout motif p il existe un ensemble fini de mots F tel que l'ensemble des mots infiniment biprolongeables évitant p + F soit uniformément récurrent (mais non vide !), et d'autre part qu'un ensemble de ce type est l'ensemble des facteurs d'un HDOL-langage. C'est par exemple ce qui se passe pour p = AA sur l'alphabet S = {a, b, c} : si on prend F = {aba, cbc}, l'ensemble des mots infiniment biprolongeables qui évitent p + F est exactement l'ensemble des facteurs d'un DOL-langage (S, mu, a) [62].
L'ensemble des couples (k, k') tel que p est k,k'-HDOL-évitable est-il toujours égal à l'ensemble des couples supérieurs ou égaux (pour l'ordre partiel) à (alphaDOL(p), alphaHDOL(p)), ou peut-il avoir une autre forme?
Préciser la structure de l'algèbre des formules et de son quotient par équivalence. Établir une classification des formules binaires.
Trouver d'autres motifs à croissance polynomiale, et leur adapter les calculs faits au chapitre 5 pour les chevauchements.
Décrire tous les motifs évités par un L-système donné.
Trouver un bon équivalent des motifs verrouillés qui rende compte des facteurs de longueur 3 (ou plus) du motif. Cela permettrait peut-être de se faire une meilleure idée sur l'existence éventuelle de motifs évitables 4-inévitables; en effet, deux points de vue opposés sont possibles actuellement :
- Les motifs verrouillés sont parmi les plus difficiles à éviter, donc comme ils sont 4-évitables tous les motifs évitables sont 4-évitables. Baker suggère même [4] que les motifs évitables qui ne sont pas divisibles par un motif verrouillé sont tous 3-évitables.
- Les motifs verrouillés ne sont pas assez difficiles à éviter, il faut concevoir d'autres familles de motifs pour espérer en trouver un 4-inévitable.

JC 1994-07-07