Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions
Fuente:
arXiv
Salvato in:
| Autori principali: | , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866912022106472448 |
|---|---|
| author | Podolskii, Vladimir Selivanov, Victor |
| author_facet | Podolskii, Vladimir Selivanov, Victor |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_06977 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions Podolskii, Vladimir Selivanov, Victor Formal Languages and Automata Theory Computational Complexity 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. |
| title | Complexity Aspects of the Extension of Wagner's Hierarchy to $k$-Partitions |
| topic | Formal Languages and Automata Theory Computational Complexity |
| url | https://arxiv.org/abs/2409.06977 |