文章基本信息

标题：On the Succinctness of Alternating Parity Good-For-Games Automata
本地全文：下载
作者：Udi Boker ; Denis Kuperberg ; Karoliina Lehtinen 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：182
页码：1-13
DOI：10.4230/LIPIcs.FSTTCS.2020.41
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：Good for games; history-determinism; alternation