Index problem for tree automata - revisited

Prelegent(ci)

Michał Skrzypczak

Afiliacja

University of Warsaw

Język referatu

angielski

Termin

27 listopada 2024 14:15

Pokój

p. 5440

Tytuł w języku polskim

Index problem for tree automata - revisited

Seminarium

Seminarium „Teoria automatów”

---

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ł.

---