论文标题
最小化良好的游戏自动机是NP完成的
Minimising Good-for-Games automata is NP complete
论文作者
论文摘要
本文讨论了以基于州的接受度找到最小的好游戏（GFG）Buchi，Co-Buchi和Parity Automata的硬性。这个问题似乎位于找到小的确定性和找到小的非确定性自动机之间，其中最小值是NP完整的和Pspace complete。但是，Radi和Kupferman的最新工作表明，以基于过渡的接受度最大程度地减少Co-Buchi自动机是可以处理的，这表明最小化GFG Automata的复杂性可能比最大程度地减少确定性自动机的复杂性更便宜。 我们表明，基于标准状态的接受性，对于Buchi，Co-Buchi和Parity GFG Automata，GFG Automaton的最小值是NP的最低性。证明是对确定性buchi自动机的证明的直接概括：它们使用类似的减少和同样的硬语言类别。
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.
