It is known that the Wadge reducibility of regular ω-languages is efficiently decidable (Krishnan et al., 1995), (Wilke, Yoo, 1995). In this paper we study analogous problem for regular k-partitions of ω-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 ω-languages and suggest a more compact way to represent them. The algorithm we provide is efficient for the more compact representation as well. © V. Podolskii, V. Selivanov.
Original languageEnglish
Pages (from-to)186-197
Number of pages12
JournalElectronic proceedings in theoretical computer science
Volume407
Issue number1
DOIs
StatePublished - 11 Sep 2024
Event14th International Workshop on Non-Classical Models of Automata and Applications - , Germany
Duration: 12 Aug 202413 Aug 2024
Conference number: 202476

    Research areas

  • Computational complexity, Problem oriented languages, Compact representation, K-partition, Preorder relation, Quadratic algorithms, RAM model, Wadge reducibility, ω-languages, Consensus algorithm

ID: 126992857