Alternating weak automata from universal trees

Laure Daviaud, Marcin Jurdziński, Karoliina Lehtinen

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Citations (Scopus)

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.

Original languageEnglish
Title of host publication30th International Conference on Concurrency Theory, CONCUR 2019
EditorsWan Fokkink, Rob van Glabbeek
PublisherSchloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
ISBN (Electronic)9783959771214
DOIs
Publication statusPublished - Aug 2019
Externally publishedYes
Event30th International Conference on Concurrency Theory, CONCUR 2019 - Amsterdam, Netherlands
Duration: 27 Aug 201930 Aug 2019

Publication series

NameLeibniz International Proceedings in Informatics, LIPIcs
Volume140
ISSN (Print)1868-8969

Conference

Conference30th International Conference on Concurrency Theory, CONCUR 2019
Country/TerritoryNetherlands
CityAmsterdam
Period27/08/1930/08/19

Keywords

  • Alternating automata
  • Büchi automata
  • Parity automata
  • Parity games
  • Universal trees
  • Weak automata

Cite this