Solving Muller Games via Safety Games

Speaker(s)

Martin Zimmermann

Affiliation

RWTH Aachen

Date

April 27, 2011, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Using results on finite-time Muller Games (which are defined using scoring
functions that measure how often a given loop in the arena has been visited) we show
how to determine the winner and a finite-state winning strategy in a Muller
game by solving a safety game. Furthermore, it turns out that one can
even determine the most general non-deterministic strategy that avoids
a certain score for the opponent. This is ongoing research and there
are several interesting open questions I could present.

---