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

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

May 10, 2017, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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.

---