Logic and
Theory of
Discrete Systems

Informatik 7

Strategies in Infinite Games

N. Chaturvedi, M. Gelderie, J. Olschewski, W. Thomas

Much of this research was carried out in the framework of the DFG Research Training Group AlgoSyn (Algorithmic Synthesis of Reactive and Discrete-Continuous Systems); other parts were supported in the final phase of by the project GASICS (Games for the Analysis and Synthesis of Interactive Computational Systems) of the European Science Foundation and (since April 2013) in the project CASSTING of the EU.

Languages and Strategies in the Context of Regular Infinite Games

In this dissertation project of J. Olschewski, finished at the end of 2012, the “complexity” of winning conditions of infinite games is related to the corresponding concept of complexity for possible winning strategies. As complexity measure, the definability in systems of (monadic second-order or first-order) logic is taken, or equivalently, language theoretical notions of definability for subclasses of the class of regular languages are applied. – In a different setting, a classification of winning strategies in infinite games was studied via a measure of nondeterminism. In a cooperation P. Bouyer and N. Markey (ENS de Cachan), it was shown that optimal strategies in this sense (called permissive strategies) can be guaranteed.

Languages and Strategies in the Context of Regular Infinite Games

In this dissertation project of J. Olschewski, finished at the end of 2012, the “complexity” of winning conditions of infinite games is related to the corresponding concept of complexity for possible winning strategies. As complexity measure, the definability in systems of (monadic second-order or first-order) logic is taken, or equivalently, language theoretical notions of definability for subclasses of the class of regular languages are applied. – In a different setting, a classification of winning strategies in infinite games was studied via a measure of nondeterminism. In a cooperation P. Bouyer and N. Markey (ENS de Cachan), it was shown that optimal strategies in this sense (called permissive strategies) can be guaranteed.

Strategy Machines

Marcus Gelderie continued his work on a new machine model for the representation of winning strategies in infinite games, called “strategy machines”, thus overcoming weaknesses of the standard representation in terms of finite automata with output (Mealy machines). Strategy machines are appropriately tailored Turing machines which induce new types of complexity analysis for strategies (in measures such as memory and latency). A focus of the recent work was the use of compositionality in strategy constructions: Here one tries to exploit the structural properties of a game arena (e.g., in the form of certain products) for a compositional construction of strategies. This work was accepted at the international conference ICALP 2013. Other work aims at devising efficient strategy machines for epsilon-optimal strategies in mean-payoff parity games and mean-penalty parity games.

Distributed Specifications and Control in the Framework of Mazurkiewicz Traces.

This doctoral project, pursued by Namit Chaturvedi, is concerned with a question left open in classical work on trace theory (more precisely, theory of Mazurkiewicz traces): How to obtain from a specification of an infinite game in terms of an infinitary regular trace language a controller that is again distributed? Important progress has been obtained by an in-depth study of deterministic asynchronous automata, and in particular, to set up an appropriate format of the transition structure which is compatible with infinitary winning conditions (like the Büchi condition).