TY - GEN
T1 - Alternating weak automata from universal trees
AU - Daviaud, Laure
AU - Jurdziński, Marcin
AU - Lehtinen, Karoliina
N1 - Funding Information:
Funding This work has been supported by the EPSRC grants EP/P020992/1 and EP/P020909/1 (Solving Parity Games in Theory and Practice).
Publisher Copyright:
© Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen.
PY - 2019/8
Y1 - 2019/8
N2 - 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.
AB - 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.
KW - Alternating automata
KW - Büchi automata
KW - Parity automata
KW - Parity games
KW - Universal trees
KW - Weak automata
UR - http://www.scopus.com/inward/record.url?scp=85071651729&partnerID=8YFLogxK
U2 - 10.4230/LIPIcs.CONCUR.2019.18
DO - 10.4230/LIPIcs.CONCUR.2019.18
M3 - Conference contribution
AN - SCOPUS:85071651729
T3 - Leibniz International Proceedings in Informatics, LIPIcs
BT - 30th International Conference on Concurrency Theory, CONCUR 2019
A2 - Fokkink, Wan
A2 - van Glabbeek, Rob
PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
T2 - 30th International Conference on Concurrency Theory, CONCUR 2019
Y2 - 27 August 2019 through 30 August 2019
ER -