1. Course Syllabus

1.1. Lectures (Weeks 1-7)

The list of topics below is tentative and will be updated based on student feedback and the overall experience in the lectures.

Automata Theory

  • Week 1: Basics of Automata Theory

    • Finite State Automata

    • Regular Languages and Closure Properties

    • Basic Characterizations such as Pumping Lemma, Myhill Nerode Theorem

    References for Week-1:

  • Week 2: Automata on Infinite Words + Connections to Logic

    • Automata on infinite words

    • S1S and WS1S

    • MSO and its decidability

    • Decidability of Presburger arithmetic

    • LTL

    References for Week-2:

  • Week 3: Tree Automata

    • Tree Automata - syntax and semantics

    • Top down v/s bottom up, determinism

    • Decision problems, Closure properties

    • Relation to parse trees of CFLs

    References for Week-3:

  • Week 4: Tree Automata and Connections to Logic

    • Infinite trees

    • S2S, and MSO over trees

    • Rewrite systems, confluence and undecidability

    • Ground rewrite systems and decidability of confluence

1.2. References.

We will closely follow these references:

Further Reading:

1.3. Papers to present at the seminars

The following is a tentative list of topics to be presented in the module. The instructor will update the list of relevant/prominent papers on these topics soon. Each week, following the first one, we will have 1-2 items presented by 1-2 attendees. If there is a paper or topic you’d like to discuss that is not in the following list, please, feel free to suggest it!

Visibly Pushdown Automata and Nested Words

Practical Algorithms for Universality and Equivalence of NFAs

Learning Regular Languages

Courcelle’s Theorem and Connections to Parametrized Complexity

Trace abstraction

Regular Model Checking

Well Structured Transition Systems

Kleene Algebra with Tests

Hyper-Properties

Symbolic Automata and Transducers

Timed and Hybrid Automata