On Repetition Languages
======================
A regular language R of finite words induces three {\em repetition languages} of infinite words: the language \lim(R), which contains words with infinitely many prefixes in R, the language \infty R, which contains words with infinitely many disjoint subwords in R, and the language R^\omega, 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\"uchi 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 \infty R, most of these problems have already been studied or are easy. We focus on R^\omega. 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^\omega is DBW-recognizable iff R^\# is \omega-regular iff R^\#=R^\omega, and there are languages for which these criteria do not hold. Thus, R^\omega need not be DBW-recognizable. In addition, when exists, the construction of a DBW for R^\omega may involve a 2^{O(n \log n)} blow-up, and deciding whether R^\omega is DBW-recognizable, for R given by a nondeterministic automaton, is PSPACE-complete. Finally, we lift the difference between R^\# and R^\omega to automata on finite words and study a variant of B\"uchi automata where a word is accepted if (possibly different) runs on it visit accepting states unboundedly many times.