This is a lecture on automata (and later other devices) that operate on infinite alphabets. The lecture is on Wednesdays at 12:15 in room 4060. The exercises are on Mondays at 14:15 in room 5050. The lecture and exercises are shared by Mikołaj Bojańczyk and Sławomir Lasota.

Lecture notes

Homework assignments

Exam

---

 

Here is an overview of the course

Data words and their automata

In the first half of the lecture, we discuss some concrete models, typically involving registers. The emptiness problem for most powerful of the models, data automata, will as hard as the famous reachability problem for vector addition systems, and the lecture will contain a description of the latter.

1. Introduction to automata with registers
2. Alternating automata with registers
3. Data automata
4. Logic on data words
5. Reachability for vector addition systems

Sets with atoms

In the second part of the lecture, we move to a more general setting, which describes some of the previous constructions in a cleaner mathematical model. This mathematical model will lead us to discover new questions.

1. Sets with atoms and orbit-finiteness
2. Automata in sets with atoms
3. Atoms with structure other than equality
4. Oligomorphism
5. What is a computable function?
6. Turing machines with atoms