Portal de Periódicos da CAPES

Ultimately periodic words of rational ω-languages

1994; Springer Science+Business Media; Linguagem: Inglês

10.1007/3-540-58027-1_27

1611-3349

Hugues Calbrix, Maurice Nivat, Andreas Podelski,

DNA and Biological Computing

In this paper we initiate the following program: Associate sets of finite words to Büchi-recognizable sets of infinite words, and reduce algorithmic problems 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 words L is sufficient to characterize L, since UP(L 1)=UP(L 2) implies L 1=L 2. We can use this fact as a test, for example, of the equivalence of two given 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 · 554-01 in the language of infinite words recognized by a given Büchi automaton.