Daviaud, Laure, Jurdzinski, Marcin and Lehtinen, MK 
ORCID: 0000-0003-1171-8790
(2019)
Alternating weak automata from universal trees.
In: 30th International Conference on Concurrency Theory.
|
Text
1903.12620v2.pdf - Published version Download (240kB) | Preview |
Abstract
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; Jurdzinski and Lazic, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough.
| Item Type: | Conference or Workshop Item (Unspecified) |
|---|---|
| Uncontrolled Keywords: | alternating automata, weak automata, B{\"u}chi automata, parity automata, parity games, universal trees |
| Depositing User: | Symplectic Admin |
| Date Deposited: | 08 Jun 2020 09:38 |
| Last Modified: | 18 Jan 2023 23:50 |
| DOI: | 10.4230/LIPIcs.CONCUR.2019.18 |
| Related URLs: | |
| URI: | https://livrepository.liverpool.ac.uk/id/eprint/3089578 |
Dimensions
Dimensions
