The Library
Optimal transformations of games and automata 2 using Muller conditions
Tools
Casares, Antonio, Colcombet, Thomas and Fijalkow, Nathanael (2021) Optimal transformations of games and automata 2 using Muller conditions. In: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), Virtual, 12–16 Jul 2021. Published in: 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 198 23:1-23:23. ISBN 9783959771955. doi:10.4230/LIPIcs.ICALP.2021.123 ISSN 1868-8969.
PDF
WRAP-optimal-transformations-Muller-conditions-Fijalkow-2021.pdf - Accepted Version Embargoed item. Restricted access to Repository staff only - Requires a PDF viewer. Download (755Kb) |
Official URL: https://doi.org/10.4230/LIPIcs.ICALP.2021.123
Abstract
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.
Item Type: | Conference Item (Paper) | ||||||
---|---|---|---|---|---|---|---|
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||
Series Name: | Leibniz International Proceedings in Informatics (LIPIcs) | ||||||
Journal or Publication Title: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | ||||||
Publisher: | Schloss Dagstuhl -- Leibniz-Zentrum | ||||||
ISBN: | 9783959771955 | ||||||
ISSN: | 1868-8969 | ||||||
Official Date: | 2 July 2021 | ||||||
Dates: |
|
||||||
Volume: | 198 | ||||||
Page Range: | 23:1-23:23 | ||||||
DOI: | 10.4230/LIPIcs.ICALP.2021.123 | ||||||
Status: | Peer Reviewed | ||||||
Publication Status: | Published | ||||||
Access rights to Published version: | Open Access (Creative Commons) | ||||||
Date of first compliant deposit: | 28 April 2021 | ||||||
Conference Paper Type: | Paper | ||||||
Title of Event: | 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) | ||||||
Type of Event: | Conference | ||||||
Location of Event: | Virtual | ||||||
Date(s) of Event: | 12–16 Jul 2021 | ||||||
Related URLs: | |||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |