# 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:
Introduction to the Theory of Computation, 3rd edition, Michael Sipser

Madhavan Mukund’s lecture notes on Automata on Infinite Words

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:
Madhavan Mukund’s lecture notes on Automata on Infinite Words

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:

Automata, Logics, and Infinite Games: A Guide to Current Research. Access this resource via NUS library #1

Theoretical Foundations of Computer Systems Boot Camp, Simons Institute for The Theory of Computing

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**

Antichains: A New Algorithm for Checking Universality of Finite Automata

Checking NFA equivalence with bisimulations up to congruence

**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**