论文标题
无限单词的自然色
Natural Colors of Infinite Words
论文作者
论文摘要
尽管有限的自动机将DFA作为一种简单而自然的正常形式，但确定性的omega-automata目前没有类似的东西。原因之一是，欧米茄常规语言的正常形式必须谈论的不仅仅是接受 - 例如，要使平均语言具有正常形式，它应该将每个无限单词与这种语言的某些自然色彩联系起来。这就提出了一个问题，即是否存在一个概念，例如无限单词的自然色（对于给定语言），并且，如果确实如此，它如何与自动机联系起来。 我们纯粹基于欧米茄的语言来定义单词的自然色彩，并在两个廉价且简单的自动机转换后，显示如何从任何确定性的平价自动机中追溯到这种自然色。由此产生的简化自动机不一定接受其自然色的每个单词，但是它具有“共同运行”，就像跑步一样，但曾经曾经可以移动到同等的语言状态，其颜色是自然色，而没有与较高颜色的共同运行。 简化的自动机针对每种颜色C定义了一个好游戏Co-BüchiAutomaton，识别其自然色W.R.T.的单词代表的语言至少是c。这为每一种$ω$ regular语言提供了一个规范的表示，因为好游戏Co-BüchiAutomata具有每种Co-Büchi语言的规范最小（并且可以获得便宜）。
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 w.r.t. 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.
