2026-07-23T14:20:21Z https://drops.dagstuhl.de/oai

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

Minimising Good-For-Games Automata Is NP-Complete Schewe, Sven Good-for-Games Automata Automata Minimisation 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sven Schewe 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.56 urn:nbn:de:0030-drops-132973 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.56 eng https://creativecommons.org/licenses/by/3.0/legalcode