Index problem for tree automata - revisited

Speaker(s)

Michał Skrzypczak

Affiliation

University of Warsaw

Language of the talk

English

Date

Nov. 27, 2024, 2:15 p.m.

Room

room 5440

Title in Polish

Index problem for tree automata - revisited

Seminar

Seminar Automata Theory

---

This talk is mostly "other people's work" type of a talk. However, it is meant to prepare ground for the next week, when Paweł Parys will present our joint results with Damian Niwiński.

I want to recall the classical problems and tools of automata theory over infinite trees. In the end, I want to give a one-page proof of a reduction from the index problem to a boundedness question (as proven originally by Colcombet-Loding). The new construction is partially based on ideas by Karoliina Lehtinen. On the way, I will mention emptiness and intersection games and guidable automata. Finally, I'll try to state the boundedness question in terms of ranks of well-founded sets, as needed by Paweł.

---