Games, logic and Automata Seminar

In this seminar we will study topics related to games, logic and automata and a rich interplay between them.

Requirements: (a) give a lecture. (b) actively participate in the lectures of other students.

We will use book Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500.

you can download the book from here

Here you can find many interesting papers. Games, logic and Automata training network

Slides Games - basic notions. slides

Talks:

27/10/10 Yoni:

Chapter 1 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. you can download the book from here

03/11/10: Itai

Chapter 3 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500.

10/11/10 Amit and 17/11/10 Nir

W. Thomas. Church's problem and a tour through automata theory. In A. Avron, N. Dershowitz, and A. Rabinovich, editors, Pillars of Computer Science, Essays Dedicated to Boris (Boaz) Trakhtenbrot on the Occasion of His 85th Birthday, volume 4800. Springer, 2008. you can download the paper from here
<

24/11/10 Moria.

H. Gimbert and W. Zielonka. Games where you can play optimally without any memory. In CONCUR 2005, volume 3653 of LNCS, pages 428-442, 2005. Springer

1/12/10 Oded

A deterministic subexponential algorithm for solving parity games Marcin Jurdzinski Mike Paterson and Uri Zwick. In SIAM Journal on Computing, 2008

8/12/10 Gilad

Nathalie Bertrand, Blaise Genest and Hugo Gimbert. Qualitative Determinacy and Decidability of Stochastic Games with Signals. In LICS 2009.

Guy 22/12/10

Krishnendu Chatterjee, Laurent Doyen. Energy Parity Games . Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), Lecture Notes in Computer Science 6199, Springer, 2010, pp. 599-610

Here are some papers for the future talks in the seminar.

Please let me know what you would like to choose.

Chapter 8. Nondeterministic Tree Automata in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500.

Uri Zwick, Michael S. Paterson, The complexity of mean payoff games on graphs Theoretical Computer Science 158, 343-359 (1996).

Nondeterministic controllers of nondeterministic processes Andre Arnold & Igor Walukiewicz, in J. Flum, E. Graedel, T. Wilke eds. "Logic and Automata", Texts in Logic and Games, Amsterdam University Press, 2007

Structured strategies in Games on graphs. R. Ramanujam and Sanil Simon in "Logic and Automata", Texts in Logic and Games, Amsterdam University Press, 2007

Chapter 12 Decidability of S1S and S2S in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500.

Kristoffer Arnsfelt Hansen, Michal Koucky and Peter Bro Miltersen. Winning Concurrent Reachability Games Requires Doubly-Exponential Patience. In LICS 2009.

Lustig and Vardi. Synthesis from Component Libraries. FOSSACS'09 .

James Gross, Frank G. Radmacher, and Wolfgang Thomas. A game-theoretic approach to routing under adversarial conditions. In Proceedings of the 6th IFIP International Conference on Theoretical Computer Science, IFIP TCS 2010, volume 323 of IFIP Advances in Information and Communication Technology, pages 355-370. Springer, 2010