We study policy iteration for infinite-horizon Markov decision processes. It has recently been
shown policy iteration style algorithms have exponential lower bounds in a two player game …

We study strategy improvement algorithms for mean-payoff and parity games. We describe a
structural property of these games, and we show that these structures can affect the …

This paper establishes a surprising reduction from parity and mean payoff games to linear
programming problems. While such a connection is trivial for solitary games, it is surprising …

Recently, temporal logics such as μ-calculus and Computational Tree Logic, CTL,
augmented with graded modalities have received attention from the scientific community …

In this thesis, we consider the problem of solving two player infinite games, such as parity
games, mean-payoff games, and discounted games, the problem of solving Markov decision …

We study the calculation of the least fixed point of systems of polynomials on semirings.
These systems arise in several branches of computer science, eg in the analysis of …

Zusammenfassung Polynomielle Systeme über Semiringen treten in verschiedenen
Bereichen der Informatik auf, so zB in der statischen Analyse prozeduraler Programme oder …

MGI - Seminar Logic, Complexity, Games: Algorithmic Aspects of Parity Games Mathematical
Foundations of Computer Science Prof. Dr. Erich Grädel Deutsch English Seminar Logic …

MGI - Seminar Logik, Komplexität, Spiele: Algorithmische Aspekte der Paritätsspiele
Mathematische Grundlagen der Informatik Prof. Dr. Erich Grädel Deutsch English Seminar …