论文标题
关于好游戏Rabin Automata的大小及其与Muller游戏中的内存链接
On the size of good-for-games Rabin automata and its link with the memory in Muller games
论文作者
论文摘要
在本文中，我们查看了识别一种穆勒语言（一种完全以每个单词中经常出现的字母集的特征的语言）的好游戏Rabin Automata。我们确定，这种自动机的最小程度与赢得具有这种语言作为其获胜条件的Muller游戏所需的最小内存的大小完全相同。我们展示了如何有效构建这种最小自动机。最后，我们确定这些自动机比同等的确定性可以更为简洁，因此证明了赢得Muller游戏的彩色内存可以比不受约束的内存大。
In this paper, we look at good-for-games Rabin automata that recognise a Muller language (a language that is entirely characterised by the set of letters that appear infinitely often in each word). We establish that minimal such automata are exactly of the same size as the minimal memory required for winning Muller games that have this language as their winning condition. We show how to effectively construct such minimal automata. Finally, we establish that these automata can be exponentially more succinct than equivalent deterministic ones, thus proving as a consequence that chromatic memory for winning a Muller game can be exponentially larger than unconstrained memory.
