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
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2022/17428/
Ehlers, Rüdiger ;
Schewe, Sven
Natural Colors of Infinite Words
Abstract
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
@InProceedings{ehlers_et_al:LIPIcs.FSTTCS.2022.36,
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 = {https://drops.dagstuhl.de/opus/volltexte/2022/17428},
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 |
