Kolmogorov's R-sets and regular tree languages

Prelegent(ci)

Michał Skrzypczak

Afiliacja

Uniwersytet Warszawski

Termin

16 kwietnia 2014 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

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.

---