Classifying $$\omega $$-Regular Aperiodic k-Partitions

Autor:	Victor L. Selivanov
Rok vydání:	2020
Předmět:	Combinatorics Hierarchy (mathematics) Aperiodic graph Structure (category theory) Omega Wadge hierarchy Decidability Mathematics
Zdroj:	Descriptional Complexity of Formal Systems ISBN: 9783030625351 DCFS
DOI:	10.1007/978-3-030-62536-8_16
Popis:	We develop a theory of \(\omega \)-regular aperiodic k-partitions (for arbitrary \(k\ge 2\)) that extends existing results for the \(\omega \)-regular k-partitions and for the fine hierarchy of regular aperiodic \(\omega \)-languages (which coincide with 2-partitions). In particular, we characterize the structure of Wadge degrees of \(\omega \)-regular aperiodic k-partitions, prove the decidability of many related problems, and discuss their complexity.
Databáze:	OpenAIRE
Externí odkaz:	https://explore.openaire.eu/search/publication?articleId=doi_________::1735c862b921b7e710ae7ec3a85cda65 https://doi.org/10.1007/978-3-030-62536-8_16 Zobrazit plný text záznamu