Marcus Gelderie (Informatik 7)
|Title||On the Complexity of Strategy Minimization in Street Games|
|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.|
- Subscribe to the ics feed.
- No Events