License: Creative Commons Attribution 3.0 Unported license (CC-BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.MFCS.2020.59
URN: urn:nbn:de:0030-drops-127268
URL: https://drops.dagstuhl.de/opus/volltexte/2020/12726/
Go to the corresponding LIPIcs Volume Portal


Kupferman, Orna ; Leshkowitz, Ofer

On Repetition Languages

pdf-format:
LIPIcs-MFCS-2020-59.pdf (0.5 MB)


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 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.

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:1--59:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Javier Esparza and Daniel Kr{\'a}ľ},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/opus/volltexte/2020/12726},
  URN =		{urn:nbn:de:0030-drops-127268},
  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


DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI