Des codes pour engendrer des langages de mots infinis

Le sujet de cette thèse est l étude des langages de mots infinis, en particulier les puissances infinies de langages de mots finis (puissance ). Plus précisément, nous nous intéressons à la question ouverte suivante : étant donné un langage L, existe-t-il un -code tel que C = L ? Cette question est l analogue de celle pour la concaténation finie : un sous-monoïde d un monoïde libre est-il engendré par un code ou non ? Dans un premier temps, nous étudions l ensemble des relateurs d un langage L, c est-à-dire les couples de factorisations différentes d un même mot de L* U L ; nous établissons une condition nécessaire pour que L ait un code ou un -code générateur. Ensuite, nous définissons une nouvelle classe de langages : les langages à un relateur. Leur ensemble de relateurs est le plus simple possible sans qu il soit des codes. Pour cette classe intéressante de langages, on caractérise les langages L tels qu il existe un -code ou un code C tels que L = C . On montre que C ne peut pas être un langage fini. Enfin, une caractérisation des codes concernant les mots infinis nous amène à définir les langages réduits ; nous considérons les propriétés de ces langages en tant que générateurs de langages de mots infinis.This thesis deals with the languages of infinite words which are the -powers of a language of finite words. In particular, we focus on the open question : given a language L, does there exist an -code C such that C = L ? It is quite similar to the question deciding whether a submonoid of a free monoid is generated by a code. First, we study the set of relations satisfied by language L, i. e. the double factorizations of a word in L* U L . We establish a necessary condition for that L has a code or an -code generator. Next, we define the new class of languages where the set of relations is as simple as possible after codes : one-relation languages. For this class of languages, we characterize the languages L such that there exists a code or an -code C such that L = C , and we show that C is never a finite language. Finally, a characterization of codes concerning infinite words leads us to define reduced languages. We consider the properties of these languages as generators of languages of infinite words.NICE-BU Sciences (060882101) / SudocSudocFranceF