LIPIcs.FSTTCS.2020.56.pdf
- Filesize: 0.52 MB
- 13 pages
Document
Minimising Good-For-Games Automata Is NP-Complete
Author
Sven Schewe 
-
Part of:
Volume:
40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2020-12-04
File
Document Identifiers
Author Details
Acknowledgements
Many thanks to Patrick Totzke and Karoliina Lehtinen for valuable feedback and pointers to beautiful related works, as well as the constructive feedback of the reviewers.
Cite As Get BibTex
Sven Schewe. Minimising Good-For-Games Automata Is NP-Complete. 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. 56:1-56:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.FSTTCS.2020.56
Abstract
This paper discusses the hardness of finding minimal good-for-games (GFG) Büchi, Co-Büchi, and parity automata with state based acceptance. The problem appears to sit between finding small deterministic and finding small nondeterministic automata, where minimality is NP-complete and PSPACE-complete, respectively. However, recent work of Radi and Kupferman has shown that minimising Co-Büchi automata with transition based acceptance is tractable, which suggests that the complexity of minimising GFG automata might be cheaper than minimising deterministic automata. We show for the standard state based acceptance that the minimality of a GFG automaton is NP-complete for Büchi, Co-Büchi, and parity GFG automata. The proofs are a surprisingly straight forward generalisation of the proofs from deterministic Büchi automata: they use a similar reductions, and the same hard class of languages.
Subject Classification
ACM Subject Classification
- Theory of computation → Automata over infinite objects
Keywords
- Good-for-Games Automata
- Automata Minimisation
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
- Marc Bagnol and Denis Kuperberg. Büchi good-for-games automata are efficiently recognizable. In Sumit Ganguly and Paritosh K. Pandya, editors, 38th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2018, December 11-13, 2018, Ahmedabad, India, volume 122 of LIPIcs, pages 16:1-16:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2018.16.
- Udi Boker and Karoliina Lehtinen. Good for Games Automata: From Nondeterminism to Alternation. In Wan Fokkink and Rob van Glabbeek, editors, 30th International Conference on Concurrency Theory (CONCUR 2019), volume 140 of Leibniz International Proceedings in Informatics (LIPIcs), pages 19:1-19:16, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CONCUR.2019.19.
-
E. Allen Emerson. Automata, tableaux and temporal logics. In Proceedings of the International Conference on Logic of Programs (ICLP 1985), 17-19 June, Brooklyn, New York, USA, volume 193 of Lecture Notes in Computer Science, pages 79-88. Springer-Verlag, 1985.
- Thomas A. Henzinger and Nir Piterman. Solving games without determinization. In Zoltán Ésik, editor, Computer Science Logic, 20th International Workshop, CSL 2006, 15th Annual Conference of the EACSL, Szeged, Hungary, September 25-29, 2006, Proceedings, volume 4207 of Lecture Notes in Computer Science, pages 395-410. Springer, 2006. URL: https://doi.org/10.1007/11874683_26.
- Tao Jiang and Bala Ravikumar. Minimal NFA problems are hard. SIAM J. Comput., 22(6):1117-1141, 1993. URL: https://doi.org/10.1137/0222067.
- Denis Kuperberg and Michał Skrzypczak. On determinisation of good-for-games automata. In Magnús M. Halldórsson, Kazuo Iwama, Naoki Kobayashi, and Bettina Speckmann, editors, Automata, Languages, and Programming - 42nd International Colloquium, ICALP 2015, Kyoto, Japan, July 6-10, 2015, Proceedings, Part II, volume 9135 of Lecture Notes in Computer Science, pages 299-310. Springer, 2015. URL: https://doi.org/10.1007/978-3-662-47666-6_24.
- Bader Abu Radi and Orna Kupferman. Minimizing GFG transition-based automata. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors, 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece, volume 132 of LIPIcs, pages 100:1-100:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.100.
- Sven Schewe. Beyond hyper-minimisation - minimising DBAs and DPAs is NP-complete. In Kamal Lodaya and Meena Mahajan, editors, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2010, December 15-18, 2010, Chennai, India, volume 8 of LIPIcs, pages 400-411. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2010. URL: https://doi.org/10.4230/LIPIcs.FSTTCS.2010.400.
- Sven Schewe. Minimising good-for-games automata is NP complete. CoRR, abs/2003.11979, 2020. URL: http://arxiv.org/abs/2003.11979.