Résumé: Nous étudions dans cette thèse les motifs évitables sur un alphabet fixe, ainsi que d'autres regularites é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 inevitables sur un alphabet donne et ayant un nombre de variables donne est toujours fini. Nous introduisons les notions de dol-evitabilite et de hdol-evitabilite, qui traduisent le lien entre l'evitabilite des motifs et les l-systemes, 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.

Paris:
Langue: Français
Collation: 181 p. ill. ;30 cm.
Diplôme: Doctorat
Etablissement de soutenance: Paris, Université Pierre et Marie Curie. Institut Blaise Pascal
Spécialité: Informatique
Index décimal 621 .Physique appliquée (électrotechnique, génie civil, génie mécanique, ingénierie appliquée, principes physiques en ingénierie)
Thème Informatique

Mots clés:
Sciences appliquées :Informatique

Note: Bibliogr. pp.161-165