Characterisation of regular tree languages on the second level of Borel hierarchy

Prelegent(ci)

Michał Skrzypczak

Afiliacja

Uniwersytet Warszawski

Termin

10 maja 2017 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

I will speak about a new result providing a relatively simple
effective characterisation of regular tree languages that belong to
the second level of the Borel hierarchy. The result is a next step
after a characterisation of the level 1.5 (Boolean combinations of
open sets) given by Bojańczyk and Place; and an
almost-characterisation of the level 1.75 (the second delta class) by
Facchini and Michalewski.

Somehow surprisingly, given how simple the final argument is, we not
only get an effective characterisation but also a Skurczyński-like
result: if a regular tree language belongs to the second level of the
Borel hierarchy then it can be recognised by an automaton of the
corresponding index. Additionally, behind the scenes, there is a new
(?) de-alternation result.

The presented results is a joint work with Filippo Cavallari (Torino +
Lausanne) and Henryk Michalewski.

---