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

Abstract

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 regular k-partitions of $\omega$-languages. In the series of previous papers (Selivanov, 2011), (Alaev, Selivanov, 2021), (Selivanov, 2012) there was a partial progress towards obtaining an efficient algorithm for deciding the Wadge reducibility in this setting as well. In this paper we finalize this line of research providing a quadratic algorithm (in RAM model). For this we construct a quadratic algorithm to decide a preorder relation on iterated posets. Additionally, we discuss the size of the representation of regular $\omega$-languages and suggest a more compact way to represent them. The algorithm we provide is efficient for the more compact representation as well.

In Proceedings NCMA 2024, arXiv:2409.06120