Mots ultimement périodiques des w-langages rationnels

H. Calbrix, M. Nivat, A. Podelski

IBP-Litp 1994/31: Rapport de Recherche Litp / Litp research reports
15 pages - Décembre/December 1994 - French document.

Titre / Title: Mots ultimement périodiques des w-langages rationnels

Résumé : Cet article est le point de départ du programme suivant : associer des ensembles de mots finis à des ensembles de mots infinis reconnaissables par automate de Büchi et réduire les problèmes algorithmiques qui se posent avec les automates de Büchi à des problèmes plus simples sur des automates de mots finis. On sait que l'ensemble UP(L) des mots ultimements périodiques d'un langage rationnel de mots infinis L suffit à caractériser celui-ci, puisque UP(L1)=UP(L2) entraine que L1=L2. On peut utiliser ce fait comme test, par exemple, de l'équivalence de deux automates de Büchi. Le principal résultat technique de cet article est la construction d'un automate qui reconnait l'ensemble de tous les mots finis u.$.v qui représentent naturellement les mots ultimement périodiques de la forme u.vw d'un langage de mots infinis reconnu par un automate de Büchi

Abstract : In this paper, we initiate the following program : associate sets of finite words to büchi-recognizable sets of infinite words, and reduce algorithmic problem on Büchi automata to simpler ones on automata on finite words. We know that the set of ultimately periodic words UP(L) of a rational language of infinite word L is sufficient to characterise L, since UP(L1)=UP(L2) implies L1=L2. We can use this fact as a test, for example, of the equivalence of two Büchi automata. The main technical result in this paper is the construction of an automaton which recognizes the set of all finite words u.$.v which naturally represent the ultimately periodic words of the form u.vw in the language of infinite words recognized by a given Büchi automaton.

Publications internes Litp 1994 / Litp research reports 1994