  This paper discusses the hardness of finding minimal good-for-games (GFG)
Buchi, Co-Buchi, 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-Buchi 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 Buchi, Co-Buchi, and parity GFG automata. The
proofs are a surprisingly straight forward generalisation of the proofs from
deterministic Buchi automata: they use a similar reductions, and the same hard
class of languages.
