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 and choose one of them to present.

Slides Games - basic notions. slides

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

Talks:

Omega-Automata. Chapter 1 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. Rotem's slides.

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

Church's Problem

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

Games of imperfect information Saleet's slides.


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

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

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

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

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

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

???

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

???

???

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).

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

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