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.FSTTCS.2018.21
URN: urn:nbn:de:0030-drops-99200
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2018/9920/
Go to the corresponding LIPIcs Volume Portal

Boker, Udi ; Lehtinen, Karoliina

On the Way to Alternating Weak Automata

pdf-format:
LIPIcs-FSTTCS-2018-21.pdf (0.5 MB)

Abstract

Different types of automata over words and trees offer different trade-offs between expressivity, conciseness, and the complexity of decision procedures. Alternating weak automata enjoy simple algorithms for emptiness and membership checks, which makes transformations into automata of this type particularly interesting. For instance, an algorithm for solving two-player infinite games can be viewed as a special case of such a transformation. However, our understanding of the worst-case size blow-up that these transformations can incur is rather poor. This paper establishes two new results, one on word automata and one on tree automata. We show that:
- Alternating parity word automata can be turned into alternating weak automata of quasi-polynomial (rather than exponential) size.
- Universal co-Büchi tree automata, a special case of alternating parity tree automata, can be exponentially more concise than alternating weak automata.
Along the way, we present a family of game languages, strict for the levels of the weak hierarchy of tree automata, which corresponds to a weak version of the canonical game languages known to be strict for the Mostowski - Rabin index hierarchy.

BibTeX - Entry

@InProceedings{boker_et_al:LIPIcs:2018:9920,
  author =	{Udi Boker and Karoliina Lehtinen},
  title =	{{On the Way to Alternating Weak Automata}},
  booktitle =	{38th IARCS Annual Conference on Foundations of Software  Technology and Theoretical Computer Science (FSTTCS 2018)},
  pages =	{21:1--21:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-093-4},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{122},
  editor =	{Sumit Ganguly and Paritosh Pandya},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2018/9920},
  URN =		{urn:nbn:de:0030-drops-99200},
  doi =		{10.4230/LIPIcs.FSTTCS.2018.21},
  annote =	{Keywords: Alternating automata, Parity games, Parity automata, Weak automata}
}

Keywords: Alternating automata, Parity games, Parity automata, Weak automata
Collection: 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2018)
Issue Date: 2018
Date of publication: 05.12.2018

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