文章基本信息

标题：Optimal Transformations of Games and Automata Using Muller Conditions
本地全文：下载
作者：Casares, Antonio ; Colcombet, Thomas ; Fijalkow, Nathanaël 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：198
DOI：10.4230/LIPIcs.ICALP.2021.123
语种：English
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We consider the following question: given an automaton or a game with a Muller condition, how can we efficiently construct an equivalent one with a parity condition? There are several examples of such transformations in the literature, including in the determinisation of Büchi automata.We define a new transformation called the alternating cycle decomposition, inspired and extending Zielonka’s construction. Our transformation operates on transition systems, encompassing both automata and games, and preserves semantic properties through the existence of a locally bijective morphism. We show a strong optimality result: the obtained parity transition system is minimal both in number of states and number of priorities with respect to locally bijective morphisms.We give two applications: the first is related to the determinisation of Büchi automata, and the second is to give crisp characterisations on the possibility of relabelling automata with different acceptance conditions.
关键词：Automata over infinite words;Omega regular languages;Determinisation of automata