Descriptive Set Theory and Computation Theory

Victor Selivanov

(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.


Wednesday 24th July 2013, 14:00
Robert Recorde Room
Department of Computer Science