Abstract |
A fundamental question in the theory of infinite two-player games is that of finding a smallest possible Mealy-automaton solution. We consider the complexity of this question and provide first results. The focus of this talk is the Streett condition, which models a strong fairness condition and captures all ω-regular languages. Two decision problems are defined and studied: “Given a Streett game, a vertex *v*_{0} in that game and an integer k in binary, does there exist a winning strategy from *v*_{0} of size at most k?” This problem is NExptime-complete. In the second problem we are given a winning strategy (from *v*_{0}) M instead of the integer k. Here we ask: “Does there exist a smaller winning strategy from *v*_{0} than M?” This problem is NP-complete. |