2026-07-25T02:31:59Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13282 2024-03-06T10:52:01Z ddc:004 open_access

On the Succinctness of Alternating Parity Good-For-Games Automata Boker, Udi Kuperberg, Denis Lehtinen, Karoliina Skrzypczak, Michał Good for games history-determinism alternation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Udi Boker and Denis Kuperberg and Karoliina Lehtinen and Michał Skrzypczak 2020 Is Part Of LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.FSTTCS.2020.41 urn:nbn:de:0030-drops-132825 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.41 eng https://creativecommons.org/licenses/by/3.0/legalcode