Standard

Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions. / Podolskii, V.; Selivanov, V.

в: Electronic proceedings in theoretical computer science, Том 407, № 1, 11.09.2024, стр. 186-197.

Результаты исследований: Научные публикации в периодических изданиях › статья в журнале по материалам конференции › Рецензирование

Harvard

Podolskii, V & Selivanov, V 2024, 'Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions', Electronic proceedings in theoretical computer science, Том. 407, № 1, стр. 186-197. https://doi.org/10.4204/EPTCS.407.13, https://doi.org/10.48550/arXiv.2409.06977

APA

Podolskii, V., & Selivanov, V. (2024). Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions. Electronic proceedings in theoretical computer science, 407(1), 186-197. https://doi.org/10.4204/EPTCS.407.13, https://doi.org/10.48550/arXiv.2409.06977

Vancouver

Podolskii V, Selivanov V. Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions. Electronic proceedings in theoretical computer science. 2024 Сент. 11;407(1):186-197. https://doi.org/10.4204/EPTCS.407.13, https://doi.org/10.48550/arXiv.2409.06977

Author

Podolskii, V. ; Selivanov, V. / Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions. в: Electronic proceedings in theoretical computer science. 2024 ; Том 407, № 1. стр. 186-197.

BibTeX

@article{ca5377461f854288ad5dd292de2eae7c,
title = "Complexity Aspects of the Extension of Wagner{\textquoteright}s Hierarchy to k-Partitions",
abstract = "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. {\textcopyright} V. Podolskii, V. Selivanov.",
keywords = "Computational complexity, Problem oriented languages, Compact representation, K-partition, Preorder relation, Quadratic algorithms, RAM model, Wadge reducibility, ω-languages, Consensus algorithm",
author = "V. Podolskii and V. Selivanov",
note = "V. Podolskii, V. Selivanov. Complexity Aspects of the Extension of Wagner's Hierarchy to k-Partitions. September 2024, Electronic Proceedings in Theoretical Computer Science 407(1):186-197, DOI: 10.4204/EPTCS.407.13; null ; Conference date: 12-08-2024 Through 13-08-2024",
year = "2024",
month = sep,
day = "11",
doi = "10.4204/EPTCS.407.13",
language = "Английский",
volume = "407",
pages = "186--197",
journal = "Electronic proceedings in theoretical computer science",
issn = "2075-2180",
publisher = "Open Publishing Association",
number = "1",

}

RIS

TY - JOUR

T1 - Complexity Aspects of the Extension of Wagner’s Hierarchy to k-Partitions

AU - Podolskii, V.

AU - Selivanov, V.

N1 - Conference code: 202476

PY - 2024/9/11

Y1 - 2024/9/11

N2 - 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.

AB - 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.

KW - Computational complexity

KW - Problem oriented languages

KW - Compact representation

KW - K-partition

KW - Preorder relation

KW - Quadratic algorithms

KW - RAM model

KW - Wadge reducibility

KW - ω-languages

KW - Consensus algorithm

UR - https://www.mendeley.com/catalogue/b6f20d68-cf0d-330a-96ee-4367d732b202/

U2 - 10.4204/EPTCS.407.13

DO - 10.4204/EPTCS.407.13

M3 - статья в журнале по материалам конференции

VL - 407

SP - 186

EP - 197

JO - Electronic proceedings in theoretical computer science

JF - Electronic proceedings in theoretical computer science

SN - 2075-2180

IS - 1

Y2 - 12 August 2024 through 13 August 2024

ER -

ID: 126992857