(A. P. Ershov Institute of Informatics Systems of Siberian Division of Russian Academy of Sciences)

We briefly discuss interaction between Descriptive Set Theory and Computation Theory. After a short historical introduction we discuss notions and methods relevant to the both fields. We will provide some additional details about infinite behaviour of finite automata, namely the Wagner hierarchy of regular omega-languages and its recent extension from the case of sets to the case of k-partitions of the Cantor space.Robert Recorde Room

Department of Computer Science