13593
Comment:
|
90461
|
Deletions are marked like this. | Additions are marked like this. |
Line 6: | Line 6: |
. [[http://www.mpi-sws.org/~rupak/|Rupak Majumdar]] ( rupak@mpi-sws.org ) Room 414, Building 26 (MPI-SWS) . [[http://www.mpi-sws.org/~neider/|Daniel Neider]] ( neider@mpi-sws.org ) Room 315, Building 26 (MPI-SWS) * '''Teaching assistants''': |
. [[http://www.mpi-sws.org/~rupak/|Dr. Rupak Majumdar]] ( rupak@mpi-sws.org ) Room 414, Building 26 (MPI-SWS) . [[http://www.mpi-sws.org/~neider/|Dr. Daniel Neider]] ( neider@mpi-sws.org ) Room 315, Building 26 (MPI-SWS) * '''Tutorials''': |
Line 10: | Line 12: |
Line 11: | Line 14: |
Line 13: | Line 17: |
Line 14: | Line 19: |
Line 15: | Line 21: |
* '''Class website''': https://wiki.mpi-sws.org/wiki/Courses/AdvancedAutomataTheory |
|
Line 16: | Line 25: |
Line 31: | Line 39: |
Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class. | Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam. |
Line 33: | Line 41: |
* '''Textbook''': . Class notes and research papers will be handed out. |
In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class. |
Line 36: | Line 43: |
The text book Michael Sipser, Introduction to the theory of computation, contains the material we will cover in the first few weeks as well as the required background for the class. | * '''Text book''' |
Line 38: | Line 45: |
* '''Teamwork''': . Students may collaborate on homeworks, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. * '''Logistics of Homework:''' . Homework exercises will be handed out every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the end of the lecture. Answers can be handed in personally to any of the teaching assistants. . |
The following text books cover most of the material (and much more): a. '''Michael Sipser''', ''Introduction to the theory of computation'', MIT Press b. '''Erich Graedel, Wolfgang Thomas, Thomas Wilke''', '' [[https://link.springer.com/book/10.1007/3-540-36387-4|Automata, Logics, and Infinite Games]]'', Springer c. '''Jeffrey Shallit''', A Second Course in Formal Languages and Automata Theory, Cambridge University Press In addition, we shall provide lecture notes, surveys, or research papers for topics not covered in these books. * '''Homework:''' Homework exercises will be handed out approximately every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture. * '''Teamwork and Academic Honesty''': Students may collaborate on homework assignments, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course. |
Line 46: | Line 61: |
* The '''written final exam''' will be held on '''July 28, 2017''' morning. (Exact time TBD.) * Homeworks are due in class! == Lecture Notes == We hope to collaboratively create Wiki-like lecture notes at https://sandstorm.init.mpg.de/shared/fE1Q2Y28_shn-nE9vet1m_xlHI2hUKjdbzlSrYEpX9c |
|
Line 48: | Line 68: |
||<rowbgcolor=""" rowstyle="#B7AFA3""2% style=""font-weight:bold; " ;text-align:center"># ||<4% style=""font-weight:bold; " ;text-align:center">Date ||<30% style=""font-weight:bold; " ;text-align:center">Course topic / lecture ||<20% style=""font-weight:bold; " ">Homework ||<35% style=""font-weight:bold; " ">Materials ||<9% style=""font-weight:bold; " ">Video || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L1 ||<style="text-align:center">April 23 ||<style="text-align:center">Introduction to formal verification || ||[[attachment:Lecture1.ppt|Lecture slides]]<<BR>>[[attachment:demillo.pdf|De Millo, Lipton, and Perlis. Social processes and proofs of programs.]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">- ||<style="text-align:center">April 25 || || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L2 ||<style="text-align:center">April 28 ||<style="text-align:center">Preliminaries: graph algorithms, automata theory ||[[attachment:hw1.pdf|Homework 1.]] Need not be turned in. ||[[attachment:Lecture2.pdf|Lecture notes]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L3 ||<style="text-align:center">April 30 ||<style="text-align:center">Preliminaries: propositional logic || ||[[attachment:Lecture3.pdf|Lecture notes]]<<BR>>[[http://ipsc.ksp.sk/2013/real/problems/l.html|Problem L (Labyrinth).]] [[https://github.com/fniksic/labyrinth|Solution]].<<BR>>[[http://try.ocamlpro.com|Try OCaml]], [[http://ocaml.org/learn/|Learn OCaml]], [[https://realworldocaml.org|Real World OCaml]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T1 ||<style="text-align:center">May 2 ||<style="text-align:center">Solutions to Homework 1. || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L4 ||<style="text-align:center">May 5 ||<style="text-align:center">The invariant verification problem. Enumerative invariant verification. Depth first search. Spin. || ||Notes from an unpublished text book by Rajeev Alur and Tom Henzinger: <<BR>> [[attachment:CavBook-1.pdf|The Reactive modules modeling language.]]<<BR>>[[attachment:CavBook-2.pdf|Invariant verification.]]<<BR>>[[http://spinroot.com/|SPIN]] web page. || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L5 ||<style="text-align:center">May 7 ||<style="text-align:center">Peterson's protocol. Heuristics for enumerative invariant verification. Symbolic invariant verification. Symbolic reachability. || ||[[attachment:CavBook-3.pdf|Alur and Henzinger. Symbolic graph representation.]] ||[[http://www.mpi-sws.org/seminars/vrs/2014-05-07_vrs.mpg|MPG (660 MB)]] || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T2 ||<style="text-align:center">May 9 ||<style="text-align:center">Q & A || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L6 ||<style="text-align:center">May 12 ||<style="text-align:center">Symbolic model checking with SAT || ||[[attachment:Sharad Malik MOD Chapter.pdf|Malik and Weissenbacher. Boolean satisfiability solvers: Techniques and extensions.]]<<BR>>[[attachment:NieOT-JACM-06.pdf|Nieuwenhuis, Oliveras, and Tinelli. Solving SAT and SAT modulo theories: From an abstract Davis-Putnam-Logemann-Loveland procedure to DPLL(T).]] ||[[http://www.mpi-sws.org/seminars/vrs/2014-05-12_vrs.mpg|MPG (678 MB)]] || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L7 ||<style="text-align:center">May 14 ||<style="text-align:center">Implementing a SAT Solver. BDDs. ||[[attachment:hw2.pdf|Homework 2.]] Due May 28, 2014. || ||[[http://www.mpi-sws.org/seminars/vrs/2014-05-14_vrs.mp4|MP4 (529 MB)]] || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T3 ||<style="text-align:center">May 16 ||<style="text-align:center">Q & A || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L8 ||<style="text-align:center">May 19 ||<style="text-align:center">BDDs. || ||[[attachment:ieeetc86.pdf|Bryant. Graph-based algorithms for Boolean function manipulation. (The BDD paper.)]] ||[[http://www.mpi-sws.org/seminars/vrs/2014-05-19_vrs.mp4|MP4 (434 MB)]] || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L9 ||<style="text-align:center">May 21 ||<style="text-align:center">SMT. Timed automata and difference constraints. || ||[[attachment:Projects.pdf|Project suggestions.]]<<BR>>[[attachment:Timed Automata.pdf|Alur, Parthasarathy. Decision problems for timed automata: A survey.]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T4 ||<style="text-align:center">May 23 ||<style="text-align:center">Q & A || || ||[[http://www.mpi-sws.org/seminars/vrs/2014-05-23_vrs.mp4|MP4 (313 MB)]] || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L10 ||<style="text-align:center">May 26 ||<style="text-align:center">Symbolic execution. || ||[[attachment:cacm13.pdf|Cadar, Sen. Symbolic execution for software testing: Three decades later.]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L11 ||<style="text-align:center">May 28 ||<style="text-align:center">Inductive invariants. Abstraction. || || || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T5 ||<style="text-align:center">May 30 ||<style="text-align:center">Solutions to Homework 2. || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L12 ||<style="text-align:center">June 2 ||<style="text-align:center">Predicate abstraction and CEGAR. || ||[[attachment:SoftwareModelChecking.pdf|Survey on software model checking.]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L13 ||<style="text-align:center">June 4 ||<style="text-align:center">IC3. ||[[attachment:hw3.pdf|Homework 3.]] Due June 18, 2014. ||[[attachment:ic3_bradley.pdf|Bradley. SAT-based model checking without unrolling. (The IC3 paper.)]]<<BR>>[[attachment:ic3_tut.pdf|Somenzi, Bradley. IC3: Where monolithic and incremental meet. (The IC3 tutorial.)]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T6 ||<style="text-align:center">June 6 ||<style="text-align:center">Q & A || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">- ||<style="text-align:center">June 9 ||<style="text-align:center">Holiday (No lecture) || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L14 ||<style="text-align:center">June 11 ||<style="text-align:center">Interpolation-based model checking || ||[[attachment:McMillan-Interpolation.pdf|McMillan. Interpolation and SAT-based model checking.]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T7 ||<style="text-align:center">June 13 ||<style="text-align:center">Discussing projects || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L15 ||<style="text-align:center">June 16 ||<style="text-align:center">Simulation and Bisimulation || ||[[attachment:partition.pdf|Partition refinement]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L16 ||<style="text-align:center">June 18 ||<style="text-align:center">Simulation and Bisimulation || || || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T8 ||<style="text-align:center">June 20 ||<style="text-align:center">Solutions to Homework 3. || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L17 ||<style="text-align:center">June 23 ||<style="text-align:center">Well-structured Transition Systems || ||[[attachment:marktoberdorf-notes.pdf|Majumdar. Marktoberdorf 2013 lecture notes.]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">- ||<style="text-align:center">June 25 ||<style="text-align:center">Cancelled. || || || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T9 ||<style="text-align:center">June 27 ||<style="text-align:center">Q & A || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L18 ||<style="text-align:center">June 30 ||<style="text-align:center">Example: Concurrent programs || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L19 ||<style="text-align:center">July 2 ||<style="text-align:center">Safe Temporal Logic (STL) ||[[attachment:hw4.pdf|Homework 4.]] Due July 9/July 16, 2014. ||[[attachment:stl.pdf|Notes on STL]] || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T10 ||<style="text-align:center">July 4 ||<style="text-align:center">Q & A || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L20 ||<style="text-align:center">July 7 ||<style="text-align:center">Model checking STL || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L21 ||<style="text-align:center">July 9 ||<style="text-align:center">Safety vs liveness ||[[attachment:Endterm.pdf|Practice exam]] ||[[attachment:safetyvsliveness.pdf|Safety and liveness]] (We did not cover all the material) || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">- ||<style="text-align:center">July 11 ||<style="text-align:center">Cancelled || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L22 ||<style="text-align:center">July 14 ||<style="text-align:center">CTL || ||[[attachment:CTL.pdf|CTL]] (For reading about linear time logics and automata: [[attachment:automata.pdf|Automata-theoretic verification]] || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L23 ||<style="text-align:center">July 16 ||<style="text-align:center">Model checking CTL ||[[attachment:exam-solutions.pdf|Solutions to the Practice Exam]] || || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T11 ||<style="text-align:center">July 18 ||<style="text-align:center">Solutions to Homework 4. '''Moved to 10:00 am!''' || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">- ||<style="text-align:center">July 21 ||<style="text-align:center">No lecture (preperation time for project presentations) || || || || ||<rowbgcolor=""" rowstyle="#F5FAFA""style="text-align:center">L24 ||<style="text-align:center">July 23 ||<style="text-align:center">Project presentations || || || || ||<rowbgcolor=""" rowstyle="#C1DAD6""style="text-align:center">T12 ||<style="text-align:center">July 25 ||<style="text-align:center">Preparation for exam ||[[attachment:hw5.pdf|Homework 5.]] (No due date) || || || |
This schedule is preliminary and subject to change. ||# ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;font-weight:bold;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">Date ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;font-weight:bold;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">Course topic / lecture ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;font-weight:bold; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">Homework ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;font-weight:bold; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">Additional Materials (lecture notes/papers) || || ||L1 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">April 18 ||Introduction to the course. Review of finite automata. Basic constructions. || ||http://www.jflap.org/ || || ||L2 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">April 19 ||Further constructions on finite automata. Regular expressions. ||[[attachment:hw1.pdf|HW1]] ||Reading: Sipser || || ||L3 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">April 25 ||Review of complexity classes, decision problems on automata || || || || ||L4 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">April 26 ||(Weak) monadic second order logics on words (WS1S). Buchi-Elgot theorem. || ||Reading: [[attachment:MukundNotesAutomataMSO.pdf|MukundNotes]] Advanced Reading: [[GraedelThomasWilke|Graedel-Thomas-Wilke]] Ch 12 || || || || || || || || || ||L5 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 02 ||Automata minimization: Homomorphisms. ||[[attachment:hw2.pdf|HW2]] ||[[attachment:lecture05_slides.pdf]] || || ||L6 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 03 ||Myhill-Nerode theorem, non-determinism. || || || || ||L7 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 09 ||Learning from examples. Passive learning. || ||[[attachment:RPNI Algorithm]] || || ||L8 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 10 ||L*. || ||[[attachment:Angluin's Algorithm]] || || ||L9 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 16 ||Applications of finite automata and learning. libalf. || || || || ||L10 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 17 ||Spill slot. || || || || || || || || || || || ||L11 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 23 ||Omega automata: Buchi, co-Buchi, Rabin, Streett. || || || || ||L12 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 24 ||Conversions between automata. Deterministic and non-deterministic automata. || || || || ||L13 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 30 ||MSO (S1S) and Buchi's theorem. || || || || ||L14 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">May 31 ||Determinization of automata. || || || || ||L15 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 06 ||Determinization of automata. || || || || ||L16 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 07 ||Alternating omega-automata: Miyano and Hayashi's construction. || || || || ||L17 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 13 ||Linear temporal logic. Automata-theoretic model checking. || || || || ||L18 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 14 ||Overflow: Applications, tools, open problems. || || || || || || || || || || || ||L19 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 20 ||Church's problem. Realizability. Games and synthesis. || || || || ||L20 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">June 21 ||Safety, reachability, Buchi, parity games. || || || || ||L21 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 04 ||Parity games and mu-calculus. || || || || ||L22 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 05 ||Bounded synthesis. || || || || ||L23 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 11 ||Tree automata and decidability of S2S || || || || ||L24 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 12 ||Beyond regularity: nested word automata. || || || || || || || || || || || ||L25 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 18 ||Context free languages. Parikh's theorem. || || || || ||L26 ||<style="" & quot; & amp; quot; & amp; amp; quot; & amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot;text-align:center& amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; amp; quot; & amp; amp; amp; amp; quot; & amp; amp; amp; quot; & amp; amp; quot; & amp; quot; & quot; "">July 19 ||Timed automata. || || || || |
Course: Advanced Automata Theory
Summer 2017
Instructor:
Dr. Rupak Majumdar ( rupak@mpi-sws.org ) Room 414, Building 26 (MPI-SWS)
Dr. Daniel Neider ( neider@mpi-sws.org ) Room 315, Building 26 (MPI-SWS)
Tutorials:
Lectures:
- Tuesdays 08:15-09:45 48-210 and Wednesdays 13:45-15:15 46-280
Tutorial: Tuesday 10:00-11:30
Office hours: By appointment
Class website: https://wiki.mpi-sws.org/wiki/Courses/AdvancedAutomataTheory
Mailing list: TBD
Introduction
Syllabus and contents.
We shall study automata on finite/infinite words and trees and their relationship to logic and computer-aided verification of systems.
Intended Audience.
Computer science or math students with background in logic and theory of computation. (Familiarity with basic algorithms, logic, and theory of computation will be assumed). Talk to the instructor if you are not sure if you have the background. We shall try to keep the class self-contained, please attend the initial lecture for background material.
Further, I expect you (1) have "mathematical maturity" (e.g., you should be comfortable with proofs and abstract reasoning); (2) are interested in the material; and (3) are willing to spend time outside of class in order to better understand the material presented in lectures.
Grading
Grading will be based on a written, open-notes, final exam. Open notes means that you are free to bring your notes to the exam. However, you may not use internet access on any device during an exam.
In order to appear for the exam, you have to turn in homework problems (to be assigned approximately biweekly), write up lecture notes for two lectures, and present a result to the class.
Text book
The following text books cover most of the material (and much more):
Michael Sipser, Introduction to the theory of computation, MIT Press b. Erich Graedel, Wolfgang Thomas, Thomas Wilke, Automata, Logics, and Infinite Games, Springer c. Jeffrey Shallit, A Second Course in Formal Languages and Automata Theory, Cambridge University Press
In addition, we shall provide lecture notes, surveys, or research papers for topics not covered in these books.
Homework:
Homework exercises will be handed out approximately every two weeks (weekday TBA). Your answers must be handed in until the day specified in the homework, at the beginning of the lecture.
Teamwork and Academic Honesty:
Students may collaborate on homework assignments, but each student needs to individually write up a solution set and be prepared to present it in class on the due date. The work you submit in this course must be the result of your individual effort. You may discuss homework problems and general proof strategies or algorithms with other students in the course, but you must not collaborate in the detailed development or actual writing of problem sets. This implies that one student should never have in his or her possession a copy of all or part of another student's homework. It is your responsibility to protect your work from unauthorized access. In writing up your homework you are allowed to use any book, paper, or published material. However, you are not allowed to ask others for specific solutions, either in person or by using electronic forums such as newsgroups. Of course, during the administration of exams any form of cooperation or help is forbidden. Academic dishonesty has no place in a university; it wastes our time and yours, and it is unfair to the majority of students. Any dishonest behavior will be severely penalized and may lead to failure in the course.
Announcements
- The first lecture is on April 18, 2017.
The written final exam will be held on July 28, 2017 morning. (Exact time TBD.)
- Homeworks are due in class!
Lecture Notes
We hope to collaboratively create Wiki-like lecture notes at https://sandstorm.init.mpg.de/shared/fE1Q2Y28_shn-nE9vet1m_xlHI2hUKjdbzlSrYEpX9c
Schedule
This schedule is preliminary and subject to change.
# |
Date |
Course topic / lecture |
Homework |
Additional Materials (lecture notes/papers) |
|
L1 |
April 18 |
Introduction to the course. Review of finite automata. Basic constructions. |
|
|
|
L2 |
April 19 |
Further constructions on finite automata. Regular expressions. |
Reading: Sipser |
|
|
L3 |
April 25 |
Review of complexity classes, decision problems on automata |
|
|
|
L4 |
April 26 |
(Weak) monadic second order logics on words (WS1S). Buchi-Elgot theorem. |
|
Reading: MukundNotes Advanced Reading: Graedel-Thomas-Wilke Ch 12 |
|
|
|
|
|
|
|
L5 |
May 02 |
Automata minimization: Homomorphisms. |
|
||
L6 |
May 03 |
Myhill-Nerode theorem, non-determinism. |
|
|
|
L7 |
May 09 |
Learning from examples. Passive learning. |
|
|
|
L8 |
May 10 |
L*. |
|
|
|
L9 |
May 16 |
Applications of finite automata and learning. libalf. |
|
|
|
L10 |
May 17 |
Spill slot. |
|
|
|
|
|
|
|
|
|
L11 |
May 23 |
Omega automata: Buchi, co-Buchi, Rabin, Streett. |
|
|
|
L12 |
May 24 |
Conversions between automata. Deterministic and non-deterministic automata. |
|
|
|
L13 |
May 30 |
MSO (S1S) and Buchi's theorem. |
|
|
|
L14 |
May 31 |
Determinization of automata. |
|
|
|
L15 |
June 06 |
Determinization of automata. |
|
|
|
L16 |
June 07 |
Alternating omega-automata: Miyano and Hayashi's construction. |
|
|
|
L17 |
June 13 |
Linear temporal logic. Automata-theoretic model checking. |
|
|
|
L18 |
June 14 |
Overflow: Applications, tools, open problems. |
|
|
|
|
|
|
|
|
|
L19 |
June 20 |
Church's problem. Realizability. Games and synthesis. |
|
|
|
L20 |
June 21 |
Safety, reachability, Buchi, parity games. |
|
|
|
L21 |
July 04 |
Parity games and mu-calculus. |
|
|
|
L22 |
July 05 |
Bounded synthesis. |
|
|
|
L23 |
July 11 |
Tree automata and decidability of S2S |
|
|
|
L24 |
July 12 |
Beyond regularity: nested word automata. |
|
|
|
|
|
|
|
|
|
L25 |
July 18 |
Context free languages. Parikh's theorem. |
|
|
|
L26 |
July 19 |
Timed automata. |
|
|
|