Document Open Access Logo

On the Succinctness of Alternating Parity Good-For-Games Automata

Authors Udi Boker, Denis Kuperberg , Karoliina Lehtinen , Michał Skrzypczak

PDF

File

Thumbnail PDF
PDF
LIPIcs.FSTTCS.2020.41.pdf
  • Filesize: 0.51 MB
  • 13 pages

Document Identifiers

Related Versions

Subject Classification

ACM Subject Classification
  • Theory of computation → Logic and verification
Keywords
  • Good for games
  • history-determinism
  • alternation

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

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.

Cite As Get BibTex

Udi Boker, Denis Kuperberg, Karoliina Lehtinen, and Michał Skrzypczak. On the Succinctness of Alternating Parity Good-For-Games Automata. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020) https://doi.org/10.4230/LIPIcs.FSTTCS.2020.41

Author Details

Udi Boker
  • Interdisciplinary Center (IDC) Herzliya, Israel
Denis Kuperberg
  • CNRS, LIP, École Normale Supérieure, Lyon, France
Karoliina Lehtinen
  • University of Liverpool, UK
Michał Skrzypczak
  • Institute of Informatics, University of Warsaw, Poland

Funding

  • Boker, Udi: Israel Science Foundation grant 1373/16.
  • Lehtinen, Karoliina: This project has received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie grant agreement No 892704.
  • Skrzypczak, Michał: Supported by Polish National Science Centre grant no. 2016/21/D/ST6/00491.

References

  1. Bader Abu Radi and Orna Kupferman. Minimizing GFG transition-based automata. In Proceedings of ICALP, pages 100:1-100:16, 2019. Google Scholar
  2. Marc Bagnol and Denis Kuperberg. Büchi good-for-games automata are efficiently recognizable. In Proceedings of FSTTCS, pages 16:1-16:14, 2018. Google Scholar
  3. Udi Boker, Denis Kuperberg, Orna Kupferman, and Michał Skrzypczak. Nondeterminism in the presence of a diverse or unknown future. In Proceedings of ICALP, pages 89-100, 2013. Google Scholar
  4. Udi Boker, Denis Kuperberg, Karoliina Lehtinen, and Michał Skrzypczak. On the succinctness of alternating parity good-for-games automata, 2020. URL: http://arxiv.org/abs/2009.14437.
  5. Udi Boker, Orna Kupferman, and Michał Skrzypczak. How deterministic are good-for-games automata? In Proceedings of FSTTCS, pages 18:1-18:14, 2017. Google Scholar
  6. Udi Boker and Karoliina Lehtinen. Good for games automata: From nondeterminism to alternation. In Proceedings of CONCUR, 2019. Google Scholar
  7. Cristian S Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li, and Frank Stephan. Deciding parity games in quasipolynomial time. In Proceedings of STOC, pages 252-263, 2017. Google Scholar
  8. Thomas Colcombet. The theory of stabilisation monoids and regular cost functions. In Proceedings of ICALP, pages 139-150, 2009. Google Scholar
  9. Thomas Colcombet. Fonctions régulières de coût. Habilitation thesis, 2013. Google Scholar
  10. Thomas Colcombet and Nathanaël Fijalkow. Universal graphs and good for games automata: New tools for infinite duration games. In Proceedings of FOSSACS, pages 1-26, 2019. Google Scholar
  11. Christian Dax and Felix Klaedtke. Alternation elimination by complementation. In Proceedings of LPAR, pages 214-229, 2008. Google Scholar
  12. Thomas Henzinger and Nir Piterman. Solving games without determinization. In Proceedings of CSL, pages 395-410, 2006. Google Scholar
  13. Simon Iosti and Denis Kuperberg. Eventually safe languages. In Proceedings of DLT, pages 192-205, 2019. Google Scholar
  14. Joachim Klein, David Müller, Christel Baier, and Sascha Klüppelholz. Are good-for-games automata good for probabilistic model checking? In Proceedings of LATA, pages 453-465, 2014. Google Scholar
  15. Denis Kuperberg and Anirban Majumdar. Computing the width of non-deterministic automata. Logical Methods in Computer Science, 15(4), 2019. Google Scholar
  16. Denis Kuperberg and Michał Skrzypczak. On determinisation of good-for-games automata. In Proceedings of ICALP, pages 299-310, 2015. Google Scholar
  17. Denis Kuperberg and Michael Vanden Boom. Quasi-weak cost automata: A new variant of weakness. In Proceedings of FSTTCS, pages 66-77, 2011. Google Scholar
  18. Karoliina Lehtinen and Martin Zimmermann. Good-for-games ω-pushdown automata. In Proceedings of the 35th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 689-702, 2020. Google Scholar
  19. Christof Löding and Stefan Repke. Decidability Results on the Existence of Lookahead Delegators for NFA. In Proceedings of FSTTCS, pages 327-338, 2013. Google Scholar
  20. Satoru Miyano and Takeshi Hayashi. Alternating finite automata on ω-words. Theoretical Computer Science, 32:321-330, 1984. Google Scholar
  21. Domenic Quirl. Bachelor Thesis, supervised by Christof Löding, RWTH Aachen, 2018. Google Scholar
Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2025 Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact