Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions

Vladimir Podolskii, Victor Selivanov

It is known that the Wadge reducibility of regular $\omega$-languages is efficiently decidable (Krishnan et al., 1995), (Wilke, Yoo, 1995). In this paper we study analogous problem for…