Alternating weak automata from universal trees

Tools

Daviaud, Laure, Jurdziński, Marcin and Lehtinen, Karoliina (2019) Alternating weak automata from universal trees. In: 30th International Conference on Concurrency Theory, CONCUR 2019. Leibniz International Proceedings in Informatics, LIPIcs . Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, NLD. ISBN 9783959771214

Full text not available from this repository.

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; Jurdziński and Lazić, 2017; and Fearnley, Jain, Schewe, Stephan, and Wojtczak, 2017), and hence it would yield a significant breakthrough.

Item Type:	Book Section
Additional Information:	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.
Uncontrolled Keywords:	alternating automata,büchi automata,parity automata,parity games,universal trees,weak automata,software ,/dk/atira/pure/subjectarea/asjc/1700/1712
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	LivePure Connector
Date Deposited:	08 Jun 2023 14:30
Last Modified:	08 Jun 2023 14:30
URI:	https://ueaeprints.uea.ac.uk/id/eprint/92339
DOI:	10.4230/LIPIcs.CONCUR.2019.18

Actions (login required)

View Item