2026-07-25T14:28:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10920 2024-03-06T10:47:11Z ddc:004 open_access

Alternating Weak Automata from Universal Trees Daviaud, Laure Jurdziński, Marcin Lehtinen, Karoliina alternating automata weak automata Büchi automata parity automata parity games universal trees An improved translation from alternating parity automata on infinite words to alternating weak automata is given. The blow-up of the number of states is related to the size of the smallest universal ordered trees and hence it is quasi-polynomial, and it is polynomial if the asymptotic number of priorities is at most logarithmic in the number of states. This is an exponential improvement on the translation of Kupferman and Vardi (2001) and a quasi-polynomial improvement on the translation of Boker and Lehtinen (2018). Any slightly better such translation would (if - like all presently known such translations - it is efficiently constructive) lead to algorithms for solving parity games that are asymptotically faster in the worst case than the current state of the art (Calude, Jain, Khoussainov, Li, and Stephan, 2017; Jurdziński and Lazić, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Laure Daviaud and Marcin Jurdziński and Karoliina Lehtinen 2019 Is Part Of LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.CONCUR.2019.18 urn:nbn:de:0030-drops-109208 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.18 eng https://creativecommons.org/licenses/by/3.0/legalcode