City Research Online

Alternating Weak Automata from Universal Trees

Daviaud, L. ORCID: 0000-0002-9220-7118, Jurdziński, M. & Lehtinen, K. (2019). Alternating Weak Automata from Universal Trees. Paper presented at the 30th International Conference on Concurrency Theory, 26-31 Aug 2019, Amsterdam, the Netherlands. doi: 10.4230/LIPIcs.CONCUR.2019.14


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 only polynomial if the asymptotic number of priorities is 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\'nski and Lazi\'c, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough.

Publication Type: Conference or Workshop Item (Paper)
Additional Information: © Laure Daviaud, Marcin Jurdziński, and Karoliina Lehtinen; licensed under Creative Commons License CC-BY.
Subjects: Q Science > QA Mathematics > QA75 Electronic computers. Computer science
Departments: School of Science & Technology > Computer Science
Text - Published Version
Available under License Creative Commons: Attribution International Public License 4.0.

Download (455kB) | Preview



Downloads per month over past year

View more statistics

Actions (login required)

Admin Login Admin Login