Time: Tuesdays 3pm to 4:50pm.

Place: MS 5117.

Contact: Itay Neeman.
Office: MS 6334.
Email:
Phone: 794-5317.
Office hours: Mondays and Wednesdays, 12noon to 1pm.
 

The topic is finite state automata and decidability, including: fsa on finite strings; fsa on infinite strings (Büchi and others) and decidability of the monadic second order theory of $\omega$ with successor; tree automata (Rabin) and decidability of the monadic second order theory of the complete binary tree with two successors.

We will mostly follow the book Automata theory and its applications by Khoussainov and Nerode.
 

List of speakers:

4/6, Duncan Palamourdas. Basic definitions, automata on finite strings, regular languages.

4/13, Pietro Carolino and Sherwood Hachtman. Pumping lemma, monadic second order (MSO) theory of finite chains, equivalence of automata and MSO formulas on chain. Büchi automata (BA), BA recognizable languages and their characterization using regular languages.

4/20, Athipat Thamrongthanyalak and Tori Noquez. Closure of BA recognizable languages under complementation, determinisitic Büchi automata (detBA), characterization of detBA recognizable languages, not every BA is equivalent to a detBA. Müller automata (MA), basic definitions and characterization of MA recognizable languages.

4/27, Tori Noquez and Siddharth Bhaskar. The McNaughton theorem, equivalence of MA and BA. Connection between BA and formulas in the monadic second order theory of one successor function (S1S), decidability of S1S.

5/4, Siddharth Bhaskar and Justin Palumbo. Equivalence of S1S and weak S1S (allowing second order quantification only over finite sets) using McNaughton theorem. Infinite games on finite graphs, definitions, forgetful strategies, putting forgetful strategies together.

5/11, Anush Tserunyan and Pietro Carolino. Proof of forgetful determinacy for infinite games on finite graphs. Game automata (GA) on trees, definitions and runs.

5/18, Pietro Carolino and Sherwood Hachtman. Rabin automata (RA), GA and RA recognizable lanauges (on trees), equivalence of RA and GA. Games and strategies on trees, ranks, open games.

5/25, Sherwood Hachtman and Anush Tserunyan. Congruence relations, strategies respecting congruence relations, deterinacy for open games using strategies respecting congruence relations. Sewing theorems, determinacy for G-delta games using strategies that respect congruence relations.

6/1, Justin Palumbo and Athipat Thamrongthanyalak. Determinacy for finite Boolean combinations of G-delta sets, via strategies that respect congruence relations using last visitation records. Forgetful determinacy for Game Automata.

6/8, Athipat Thamrongthanyalak and Siddharth Bhaskar. Complementation theorem for RA recognizable tree languages. S2S, the monadic second order theory of the complete binary tree. Decidability of S2S. Applications including the decidability of the monadic second order theory of the reals with second order variables limited to Boolean combinations of F-sigma and G-delta sets.