Mots ultimement periodiques des langages rationnels de mots infinis.

H. Calbrix

IBP-Litp 1996/Th/03: THÈSE de DOCTORAT de l'UNIVERSITÉ PARIS 6 Litp / Litp research reports
126 pages - Avril/April 1996 - French document.

PostScript : Ko /Kb

Titre / Title: Mots ultimement periodiques des langages rationnels de mots infinis.

Résumé : Le travail de recherche exposé dans ce mémoire a pour point de départ deux constatations:
d'une part, un langage rationnel de mots infinis est caractérisé par l'ensemble de ses mots ultimement périodiques, et d'autre part, un mot ultimement périodique peut être représenté par un mot fini. Du rapprochement de ces deux faits est née l'idée de représenter les langages rationnels de mots infinis par des langages de mots finis. Nous montrons, en utilisant trois opérateurs (puissance, racine et conjugaison), que ces langages de représentations finies sont rationnels, puis nous caractérisons ces langages a l'aide d'une relation d'équivalence identifiant les mots finis représentant le même mot ultimement périodique. Cette approche produit une construction du monoïde syntaxique d'un langage rationnel de mots infinis, ainsi qu'une nouvelle méthode de décision de la logique S1S. Enfin, nous définissons les langages de périodes et de préfixes associés a un langage rationnel de mots infinis. Les premiers sont caractérises à l'aide de trois opérateurs, similaires aux précédents, et nous donnons une condition nécessaire vérifiée par les seconds.

Abstract : The starting point of this research work is the following two facts: on one hand, a rational w-language is characterized by the set of its ultimately periodic words, and on the other hand, an ultimately periodic word can be represented by a finite word. The natural idea is then to represent rational w-languages by finite words languages. We define thre operators (power, root and conjugacy) to show that these finite words representations are rational. Then we define an equivalence and we use this relation to characterize the finite representations languages. We obtain a method to construct the syntactic congruence of a rational w-language and a new decision procedure to decide S1S theory. Then we define the period and prefix languages associated to a rational w-language. We define three operators, similar to the first ones, to characterize period languages and we give a necessary condition which is verified by the prefix languages.

Publications internes Litp 1996 / Litp research reports 1996