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 or Highlights of logics, games automata and choose one of them to present.

Here are the slides I presented on Logic - basic notions. slides

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

Assaf 22/3: Chapter 1 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500 Assaf's slides.

Jonathan Cederbaum 29/3: Chapter 2 in Automata, Logic and infinite games, slides

Lior Zilberstein 19/4: Parity Games. Chapter 6 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. slides

Yogev Bar-On 26/4: 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. slides

Uri Avron 3/5: A deterministic subexponential algorithm for solving parity games Marcin Jurdzinski Mike Paterson and Uri Zwick. In SIAM Journal on Computing, 2008 and Jurdzinski. Algorithms for Solving Parity Games. In Lectures in Game Theory for Computer Scientists ed. Krzysztof R. Apt, Erich Grädel. 2011. slides

Tal Shuster 10/5: Chapter 8. Nondeterministic Tree Automata in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. slides

Lior Schneider 17/5: Chapter 9. Alternating Tree Automata in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. slides

Ayelet 24/5: Laurent Doyen and Jean-François Raskin. Games with Imperfect Information: Theory and Algorithms . Lectures in Game Theory for Computer Scientists. Cambridge University Press, 2011, pp. 185-212.

David Lederkremer, 7/6: 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 slides

Itay 14/6/2007: Thomas Colcombet, Nathanaël Fijalkow, and Florian Horn. “Playing Safe”. In: FSTTCS 2014: Foundations of Software Technology and Theoretical Computer Science. Edited by Venkatesh Raman and S. P. Suresh. Volume 29. LIPICs. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2014, pages 379–390. slides

Doron Tiferet 21/6: H. Gimbert and F. Horn. Solving simple stochastic tail games. In Proceedings of SODA, pages 847–862. SIAM, 2010

Keren???: Orna Kupferman Automata Theory and Model Checking (closure under complementation Sect 2)

A. J. Lazarus, D. E. Loeb, J. G. Propp, and D. Ullman. Richman games. and part of A. J. Lazarus, D. E. Loeb, J. G. Propp, W. R. Stromquist, and D. H. Ullman. Combinatorial games under auction play. Games and Economic Behavior, 27(2):229–264, 1999 29:439–449, 1996.

More topics

Krishnendu Chatterjee, Laurent Doyen, Hugo Gimbert, and Youssouf Oualhadj. Perfect-Information Stochastic Mean-Payoff Parity Games. Proceedings of the 17th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), Lecture Notes in Computer Science 8412, Springer, 2014, pp. 210-225.

K. Etessami "Analysis of Probabilistic Processes and Automata Theory". DRAFT of Chapter in forthcoming Handbook of Automata Theory, editor Jean-Eric Pin, European Mathmatical Society publishing (EMS) (ONLY part of this survey should be covered in the presentation)

Strategy Complexity of Concurrent Stochastic Games with Safety and Reachability Objectives Krishnendu Chatterjee, Kristoffer Arnsfelt Hansen, Rasmus Ibsen-Jensen

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

Amir Pnueli, Roni Rosner: On the Synthesis of a Reactive Module. POPL 1989: 179-190

Uri Klein, Nir Piterman, Amir Pnueli: Effective Synthesis of Asynchronous Systems from GR(1) Specifications. VMCAI 2012: 283-298