Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
<|reference_start|>Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions: 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.<|reference_end|>
@article{podolskii2024complexity,
    title={Complexity Aspects of the Extension of Wagner's Hierarchy to
  $k$-Partitions},
    author={Vladimir Podolskii, Victor Selivanov},
    journal={EPTCS 407, 2024, pp. 186-197},
    year={2024},
    doi={10.4204/EPTCS.407.13},
    archivePrefix={arXiv},
    eprint={2409.06977},
    primaryClass={cs.FL cs.CC}
}