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.2020.41
URN: urn:nbn:de:0030-drops-132825
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/13282/
Boker, Udi ;
Kuperberg, Denis ;
Lehtinen, Karoliina ;
Skrzypczak, MichaĆ
On the Succinctness of Alternating Parity Good-For-Games Automata
Abstract
We study alternating parity good-for-games (GFG) automata, i.e., alternating parity automata where both conjunctive and disjunctive choices can be resolved in an online manner, without knowledge of the suffix of the input word still to be read.
We show that they can be exponentially more succinct than both their nondeterministic and universal counterparts. Furthermore, we present a single exponential determinisation procedure and an Exptime upper bound to the problem of recognising whether an alternating automaton is GFG.
We also study the complexity of deciding "half-GFGness", a property specific to alternating automata that only requires nondeterministic choices to be resolved in an online manner. We show that this problem is PSpace-hard already for alternating automata on finite words.
BibTeX - Entry
@InProceedings{boker_et_al:LIPIcs:2020:13282,
author = {Udi Boker and Denis Kuperberg and Karoliina Lehtinen and Micha{\l} Skrzypczak},
title = {{On the Succinctness of Alternating Parity Good-For-Games Automata}},
booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)},
pages = {41:1--41:13},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-174-0},
ISSN = {1868-8969},
year = {2020},
volume = {182},
editor = {Nitin Saxena and Sunil Simon},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/13282},
URN = {urn:nbn:de:0030-drops-132825},
doi = {10.4230/LIPIcs.FSTTCS.2020.41},
annote = {Keywords: Good for games, history-determinism, alternation}
}
Keywords: |
|
Good for games, history-determinism, alternation |
Collection: |
|
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) |
Issue Date: |
|
2020 |
Date of publication: |
|
04.12.2020 |