DOI

We study relationships of monotone well quasiorders to regular languages and ω-languages, concentrating on decidability of the lattices of upper sets on words and infinite words. We establish rather general sufficient conditions for decidability. Applying these conditions to concrete natural monotone WQOs, we obtain new decidability results and new proofs of some known results.
Original languageEnglish
Title of host publicationDescriptional Complexity of Formal Systems
Pages235-247
Number of pages13
DOIs
StatePublished - 1 Jan 2019
Event21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019 - Košice, Slovakia
Duration: 17 Jul 2019 → 19 Jul 2019

Publication series

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

Conference

Conference21st International Conference on Descriptional Complexity of Formal Systems, DCFS 2019
Country/TerritorySlovakia
CityKošice
Period17/07/19 → 19/07/19

    Research areas

  • Decidability, Difference hierarchy, Lattice of upper sets, Monotone WQO, Periodic extension, Regular language

ID: 126994992