Abstract
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 ∞ 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 ∞ 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 DBWrecognizable iff R^# is ωregular iff R^# = R^ω, and there are languages for which these criteria do not hold. Thus, R^ω need not be DBWrecognizable. In addition, when exists, the construction of a DBW for R^ω may involve a 2^{O(n log n)} blowup, and deciding whether R^ω is DBWrecognizable, for R given by a nondeterministic automaton, is PSPACEcomplete. 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.
BibTeX  Entry
@InProceedings{kupferman_et_al:LIPIcs:2020:12726,
author = {Orna Kupferman and Ofer Leshkowitz},
title = {{On Repetition Languages}},
booktitle = {45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
pages = {59:159:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771597},
ISSN = {18688969},
year = {2020},
volume = {170},
editor = {Javier Esparza and Daniel Kr{\'a}ľ},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12726},
URN = {urn:nbn:de:0030drops127268},
doi = {10.4230/LIPIcs.MFCS.2020.59},
annote = {Keywords: B{\"u}chi automata, Expressive power, Succinctness}
}
Keywords: 

Büchi automata, Expressive power, Succinctness 
Collection: 

45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020) 
Issue Date: 

2020 
Date of publication: 

18.08.2020 