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
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.
Sets with atoms
- Introduction to automata with registers
- Alternating automata with registers
- Data automata
- Logic on data words
- Reachability for vector addition systems
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.
- Sets with atoms and orbit-finiteness
- Automata in sets with atoms
- Atoms with structure other than equality
- What is a computable function?
- Turing machines with atoms