Kolmogorov's R-sets and regular tree languages

Speaker(s)

Michał Skrzypczak

Affiliation

Uniwersytet Warszawski

Date

April 16, 2014, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

R-sets, introduced in 1928 by Andrey Kolmogorov, were designed as a wide class of well-behaved sets that can be described in a constructible way. One of the crucial properties of this class is universal measurability (in particular Lebesgue measurability).

It turns out that certain regular tree languages, namely W_{i,k}, are complete for finite levels of the hierarchy of R-sets. First of all, it gives us a sequence of very natural examples of R-sets. Additionally, we obtain the following new theorem: every regular tree language is universally measurable.

The relation between the W_{i,k} languages and R-sets relies on a game-theoretic approach to R-sets: in a certain sense, R-sets are equivalent to parity games. Therefore, one may risk a statement that parity games date back to Kolmogorov in '20 of the previous century.

The talk is based on joint work with T. Gogacz, H. Michalewski, and M. Mio.

---