Paper Info
Title
Ultimately Periodic Words of Rational w-Languages
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 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.
Year
DOI
Venue
1993
10.1007/3-540-58027-1_27
MFPS
Keywords
Field
DocType
rational w-languages,periodic words
Discrete mathematics,Deterministic automaton,Sequence,Automaton,Finite-state machine,Equivalence (measure theory),Regular language,Periodic graph (geometry),Mathematics,Büchi automaton
Conference
ISBN
Citations 
PageRank 
3-540-58027-1
17
0.89
References 
Authors
2
3
Name
Order
Citations
PageRank
Hugues Calbrix1342.63
Maurice Nivat21261277.74
Andreas Podelski32760197.87