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.

Here you can find many interesting papers. Games, logic and Automata training network and choose one of them to present.

Slides Games - basic notions. slides

Talks:

09/11/11 Gilad:

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

16/11/2011 Michael

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. Michael's slides

23/11/2011 Ghila

Determinization of Buchi-Automata. You can use Chapter 3 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. Ghila's slides

30/11/2011 Rotem

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

7/12/2011 Dean Doron

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

14/12/2011 Omri

N. Fijalkow and F. Horn. The surprizing complexity of reachability games. slides

21/12/2011 Eytan

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

28/12/2011 Barak

Applications of decidability of S2S.

to be scheduled Pavel

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

to be scheduled Eyal

J. Fearnley and M. Zimmermann. Playing Muller Games in a Hurry

Here are some papers for the future talks in the seminar. Please let me know what you would like to choose.

???

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

???

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

P. Madhusudan: Synthesizing Reactive Program. In CSL 2011.

Julien Cristau and Florian Horn. Graph Games on Ordinals. In Proceedings of the 28th Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS'08

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

D. M. Gabbay, A. Pnueli, S. Shelah, J. Stavi. On the Temporal Analysis of Fairness. 7th POPL, pp. 163-173, 1980.

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

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

Y. Lustig, S. Nain and Vardi. Synthesis from Probabilistic Components CSL'11 .

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