课程摘要：
In my mini-course, I will show how the humble finite automaton is, in fact, an extraordinarily flexible machine, which can be adapted to objects such as infinite words or trees, and enjoys an interesting and mathematically non-trivial theory. Also, there is a deep connection between automata and other fields, such as logic and semigroup theory. The mini-course will consist of four parts, each one with two hours.
课程大纲：
1. Automata and their connection to logic. (10月14日下午3:00-5:00, 北大智华楼109教室)
I will begin by briefly recalling finite automata, and the languages that are recognised by them, namely the regular languages. Then, I will show that the same languages can be described using logic, with expressions like “there last position has label a, but there are no two consecutive positions that have label a”.
2. Infinite words (10月15日下午3:00-5:00, 北大智华楼109教室)
We will discuss automata and logic on infinite words. The idea is that an infinite word describes a run of a system that runs (or at least is supposed to run) forever, like a controller. For infinite words, automata constructions such as determinization become mathematically much more interesting than in the finite case.
3. Infinite trees (10月16日下午3:00-5:00, 中国科学院软件研究所5号楼334报告厅)
We will prove the Rabin theorem, which extends the theory of automata and logic to infinite trees. In the analysis leading up to this theorem, an important role is played by games of infinite duration. These are interesting in and of themselves, and are subtle enough to raise paradoxes, such as games where nobody can win, despite full information and no draws. .
4. Transducers (10月17日下午3:00-5:00, 中国科学院软件研究所5号楼334报告厅)
The first three parts discuss automata as language acceptors, which means that the output is either “yes” or “no”. In the last part, I will discuss automata with more complicated outputs, typically numbers, words or trees. Such automata are called transducers.
授课老师简介：
Mikołaj Bojańczyk is a full professor at the Institute of Informatics at the University of Warsaw, Poland. He works on logic in computer science, with a focus on automata. He is a famous researcher on automata theory. He has won many awards, including Ackermann Award, Presburger Award, ICALP Best Paper Award, PODS Best Paper and Test of Time Award. He has published more than 40 papers in the top theoretical computer science conferences including LICS and ICALP. More information can be found at https://www.mimuw.edu.pl/~bojan/.
