Author: Victor Selivanov

Title:  Classifying omega-Regular Partitions
 
Abstract: We try to develop a theory of $\omega$-regular  partitions in
parallel with the theory around the Wagner hierarchy of regular
$\omega$-languages. In particular, we generalize a theorem of L.
Staiger and K. Wagner to the case of partitions, prove decidability
of all levels of the Boolean hierarchy of regular partitions over
open sets, establish coincidence of reducibilities by continuous
functions and by functions computed by finite automata on the class
of regular ${\bf\Delta}^0_2$-partitions, and show undecidability of
the first-order theory of the structure of Wadge degrees of regular
$k$-partitions for all $k>2$.