License: Creative Commons Attribution 4.0 International license (CC BY 4.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2022.36
URN: urn:nbn:de:0030-drops-174280
Go to the corresponding LIPIcs Volume Portal

Ehlers, Rüdiger ; Schewe, Sven

Natural Colors of Infinite Words

LIPIcs-FSTTCS-2022-36.pdf (0.7 MB)


While finite automata have minimal DFAs as a simple and natural normal form, deterministic omega-automata do not currently have anything similar. One reason for this is that a normal form for omega-regular languages has to speak about more than acceptance - for example, to have a normal form for a parity language, it should relate every infinite word to some natural color for this language. This raises the question of whether or not a concept such as a natural color of an infinite word (for a given language) exists, and, if it does, how it relates back to automata.
We define the natural color of a word purely based on an omega-regular language, and show how this natural color can be traced back from any deterministic parity automaton after two cheap and simple automaton transformations. The resulting streamlined automaton does not necessarily accept every word with its natural color, but it has a "co-run", which is like a run, but can once move to a language equivalent state, whose color is the natural color, and no co-run with a higher color exists.
The streamlined automaton defines, for every color c, a good-for-games co-Büchi automaton that recognizes the words whose natural colors with respect to the represented language are at least c. This provides a canonical representation for every ω-regular language, because good-for-games co-Büchi automata have a canonical minimal - and cheap to obtain - representation for every co-Büchi language.

BibTeX - Entry

  author =	{Ehlers, R\"{u}diger and Schewe, Sven},
  title =	{{Natural Colors of Infinite Words}},
  booktitle =	{42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)},
  pages =	{36:1--36:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-261-7},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{250},
  editor =	{Dawar, Anuj and Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{},
  URN =		{urn:nbn:de:0030-drops-174280},
  doi =		{10.4230/LIPIcs.FSTTCS.2022.36},
  annote =	{Keywords: parity automata, automata over infinite words, \omega-regular languages}

Keywords: parity automata, automata over infinite words, ω-regular languages
Collection: 42nd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2022)
Issue Date: 2022
Date of publication: 14.12.2022

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