You are not logged in |
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.
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.
