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.

Additional book: An Automata Toolbox by Bojanczyk and Czerwinski

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.

Omer and Lavi, 14/3 Chapter 1 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500

Rom: 21/3. Chapter 2 in Automata, Logic and infinite games,

Itay, 26/3: Parity Games. Chapter 6 in Automata, Logic and infinite games, edited by Gradel, Thomas and Wilke, LNCS 2500. or Chapter 2 in Automata toolbox Itay's slides.

Eitan, 11/04/18 Parity games in quasipolynomial time - Chapter 3 in An Automata Toolbox. Eitan's slides. and Eitan's notes

Daniel 25/04/18 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) ONLY SECTs 3 and 4 about Finite state Markov processes and MSP should be presented.

Nitay, 2/5: An Automata Toolbox Chapter 5 monadic logic

Lior 9/5 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

Or 23/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.

Omri??? 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.

Orna Kupferman Automata Theory and Model Checking (closure of regular languages under boolean operations, complementation Sect 2)

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.

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

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.

H. Gimbert and F. Horn. Solving simple stochastic tail games. In Proceedings of SODA, pages 847–862. SIAM, 2010

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. or A.J. Lazarus, D.E. Loeb, J.G. Propp, D.H. Ullman Richman games

Distributed synthesis is simply undecidable - by S Schewe -2014 Information Processing Letters Volume 114, Issue 4, April 2014, Pages 203-207

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

More topics