论文标题
穆勒条件的最佳转换
Optimal Transformations of Muller Conditions
论文作者
论文摘要
在本文中，我们对无限单词和无限持续时间游戏感兴趣，我们将其视为通用过渡系统。我们使用穆勒条件研究系统的转换，并使用平等条件来扩展Zielonka的构造。我们介绍了交替的周期分解转换，并且证明了强大的最佳结果：对于任何给定的确定性muller自动机，所获得的奇偶校验自动机在大小和优先级中的优先级最少，而自动机则将形态纳入原始的muller automaton中。 我们提供两个申请。首先是Piterman和Schewe确定Büchi自动机为平等自动机的改进。第二个是介绍有关在不同接受条件下重新标记自动机的可能性的特征。
In this paper, we are interested in automata over infinite words and infinite duration games, that we view as general transition systems. We study transformations of systems using a Muller condition into ones using a parity condition, extending Zielonka's construction. We introduce the alternating cycle decomposition transformation, and we prove a strong optimality result: for any given deterministic Muller automaton, the obtained parity automaton is minimal both in size and number of priorities among those automata admitting a morphism into the original Muller automaton. We give two applications. The first is an improvement in the process of determinisation of Büchi automata into parity automata by Piterman and Schewe. The second is to present characterisations on the possibility of relabelling automata with different acceptance conditions.
