License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CONCUR.2019.18
URN: urn:nbn:de:0030-drops-109208
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10920/
Go to the corresponding LIPIcs Volume Portal

Daviaud, Laure ; Jurdzinski, Marcin ; Lehtinen, Karoliina

Alternating Weak Automata from Universal Trees

pdf-format:
LIPIcs-CONCUR-2019-18.pdf (0.4 MB)

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.

BibTeX - Entry

@InProceedings{daviaud_et_al:LIPIcs:2019:10920,
  author =	{Laure Daviaud and Marcin Jurdzinski and Karoliina Lehtinen},
  title =	{{Alternating Weak Automata from Universal Trees}},
  booktitle =	{30th International Conference on Concurrency Theory (CONCUR 2019)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-121-4},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{140},
  editor =	{Wan Fokkink and Rob van Glabbeek},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2019/10920},
  URN =		{urn:nbn:de:0030-drops-109208},
  doi =		{10.4230/LIPIcs.CONCUR.2019.18},
  annote =	{Keywords: alternating automata, weak automata, B{\"u}chi automata, parity automata, parity games, universal trees}
}

Keywords: alternating automata, weak automata, Büchi automata, parity automata, parity games, universal trees
Collection: 30th International Conference on Concurrency Theory (CONCUR 2019)
Issue Date: 2019
Date of publication: 20.08.2019

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI