Motifs évitables et régularités dans les mots
Résumé
Nous étudions dans cette thèse les motifs évitables sur un alphabet fixé,
ainsi que d'autres régularités évitables ou non. En particulier, nous
présentons une classification complète des motifs binaires et un début de
classification des motifs ternaires; nous prouvons par ailleurs que l'ensemble
des motifs inévitables sur un alphabet donné et ayant un nombre de variables
donné est toujours fini. Nous introduisons les notions de DOL-évitabilité et
de HDOL-évitabilité, qui traduisent le lien entre l'évitabilité des motifs et
les L-systèmes, et nous montrons que sous certaines conditions on peut décider
si un HDOL-langage évite un motif. Nous abordons également deux problèmes plus
combinatoires, celui du dénombrement des mots évitant un motif, dans le cas
particulier des chevauchements, et celui de la construction de suites de
complexité donnée.
Mots-clés
Théorie des langages, Combinatoire, Mot, Motif évitable, Décidabilité,
L-système, Chevauchement, Complexité de suites, Suite régulière,
Facteur spécial.
JC 1994-07-07