Differences between revisions 42 and 46 (spanning 4 versions)
Revision 42 as of 2017-05-03 06:32:47
Size: 48972
Editor: rupak
Comment:
Revision 46 as of 2017-05-08 12:33:08
Size: 103720
Editor: neider
Comment:
Deletions are marked like this. Additions are marked like this.
Line 61: Line 61:
 * The '''written final exam''' will be held on '''July 28, 2017''' morning. (Exact time TBD.)
 * Homeworks are due in class!
Line 67: Line 69:
||# ||<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;font-weight:bold;text-align:center&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;font-weight:bold;text-align:center&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;font-weight:bold; &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;font-weight:bold; &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;text-align:center&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;text-align:center&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;text-align:center&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;text-align:center&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 || ||
||# ||<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; &amp; 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; amp; amp; amp; quot;font-weight:bold;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;font-weight:bold;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;font-weight:bold;      &amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;font-weight:bold; &amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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 || ||
Line 73: Line 75:
||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;text-align:center&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: Myhill-Nerode theorem, non-determinism. ||[[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;text-align:center&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 ||Automata learning: Passive learning, L*. || || || ||
||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;text-align:center&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 ||Applications of finite automata and learning. libalf. || || || ||
||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;text-align:center&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 ||Spill slot. || || || ||
||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;text-align:center&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 ||Omega automata: Buchi, co-Buchi, Rabin, Streett. || || || ||
||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;text-align:center&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 ||Conversions between automata. Deterministic and non-deterministic automata. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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*. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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. || || || ||
Line 80: Line 82:
||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;text-align:center&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 ||MSO (S1S) and Buchi's theorem. || || || ||
||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;text-align:center&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 ||Determinization of 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;text-align:center&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 ||Determinization of automata. || || || ||
||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;text-align:center&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 ||Alternating omega-automata: Miyano and Hayashi's construction. || || || ||
||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;text-align:center&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 ||Linear temporal logic. Automata-theoretic model checking. || || || ||
||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;text-align:center&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 ||Overflow: Applications, tools, open problems. || || || ||
||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;text-align:center&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 ||Church's problem. Realizability. Games and synthesis. || || || ||
||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;text-align:center&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 ||Safety, reachability, Buchi, parity games. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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. || || || ||
Line 89: Line 91:
||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;text-align:center&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 ||Parity games and mu-calculus. || || || ||
||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;text-align:center&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 ||Bounded synthesis. || || || ||
||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;text-align:center&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 ||Tree automata and decidability of S2S || || || ||
||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;text-align:center&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 ||Beyond regularity: nested word automata. || || || ||
||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;text-align:center&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 ||Context free languages. Parikh's theorem. || || || ||
||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;text-align:center&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 ||Timed automata. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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. || || || ||
Line 96: Line 98:
||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;text-align:center&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 ||TBD. || || || ||
||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;text-align:center&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 ||TBD. || || || ||
||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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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; &amp; 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; amp; amp; amp; quot;text-align:center&amp; amp; 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; amp; amp; quot; &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

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

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

http://www.jflap.org/

L2

April 19

Further constructions on finite automata. Regular expressions.

HW1

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.

HW2

lecture05_slides.pdf

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.

Courses/AdvancedAutomataTheory-SS2017 (last edited 2018-03-29 06:38:49 by neider)