DOI

We develop a theory of regular aperiodic k-partitions (for arbitrary that extends existing results for the regular k-partitions and for the fine hierarchy of regular aperiodic languages (which coincide with 2-partitions). In particular, we characterize the structure of Wadge degrees of regular aperiodic k-partitions, prove the decidability of many related problems, and discuss their complexity.
Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems
Pages193-205
Number of pages13
DOIs
StatePublished - 1 Jan 2020
Event22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020 - Vienna, Austria
Duration: 24 Aug 2020 → 26 Aug 2020

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
PublisherSpringer Nature
Volume12442
ISSN (Print)0302-9743

Conference

Conference22nd International Conference on Descriptional Complexity of Format Systems, DCFS 2020
Country/TerritoryAustria
CityVienna
Period24/08/20 → 26/08/20

    Research areas

  • Acceptor, Aperiodic k-partition, Fine hierarchy, Iterated labeled tree, Reducibility, Transducer

ID: 126991279