摘要：A regular language R of finite words induces three repetition languages of infinite words: the language lim(R), which contains words with infinitely many prefixes in R, the language â^Z R, which contains words with infinitely many disjoint subwords in R, and the language R^Ï, which contains infinite concatenations of words in R. Specifying behaviors, the three repetition languages provide three different ways of turning a specification of a finite behavior into an infinite one. We study the expressive power required for recognizing repetition languages, in particular whether they can always be recognized by a deterministic Büchi word automaton (DBW), the blow up in going from an automaton for R to automata for the repetition languages, and the complexity of related decision problems. For lim R and â^Z R, most of these problems have already been studied or are easy. We focus on R^Ï. Its study involves some new and interesting results about additional repetition languages, in particular R^#, which contains exactly all words with unboundedly many concatenations of words in R. We show that R^Ï is DBW-recognizable iff R^# is Ï-regular iff R^# = R^Ï, and there are languages for which these criteria do not hold. Thus, R^Ï need not be DBW-recognizable. In addition, when exists, the construction of a DBW for R^Ï may involve a 2^{O(n log n)} blow-up, and deciding whether R^Ï is DBW-recognizable, for R given by a nondeterministic automaton, is PSPACE-complete. Finally, we lift the difference between R^# and R^Ï to automata on finite words and study a variant of Büchi automata where a word is accepted if (possibly different) runs on it visit accepting states unboundedly many times.
