On the Complexity of Strategy Minimization in Street Games

Speaker

Marcus Gelderie (Informatik 7)

Title On the Complexity of Strategy Minimization in Street Games
When 20.04.2011, 10:00
Where Room 5052
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 v0 in that game and an integer k in binary, does there exist a winning strategy from v0 of size at most k?” This problem is NExptime-complete. In the second problem we are given a winning strategy (from v0) M instead of the integer k. Here we ask: “Does there exist a smaller winning strategy from v0 than M?” This problem is NP-complete.
Slides