Well-Quasi-Orderings on Word Languages
Fuente:
arXiv
Salvato in:
| Autori principali: | , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866929674265821184 |
|---|---|
| author | Lhote, Nathan Lopez, Aliaume Schütze, Lia |
| author_facet | Lhote, Nathan Lopez, Aliaume Schütze, Lia |
| contents | The set of finite words over a well-quasi-ordered set is itself well-quasi-ordered. This seminal result by Higman is a cornerstone of the theory of well-quasi-orderings and has found numerous applications in computer science. However, this result is based on a specific choice of ordering on words, the (scattered) subword ordering. In this paper, we describe to what extent other natural orderings (prefix, suffix, and infix) on words can be used to derive Higman-like theorems. More specifically, we are interested in characterizing languages of words that are well-quasi-ordered under these orderings. We show that a simple characterization is possible for the prefix and suffix orderings, and that under extra regularity assumptions, this also extends to the infix ordering. We furthermore provide decision procedures for a large class of languages, that contains regular and context-free languages. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2501_07428 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Well-Quasi-Orderings on Word Languages Lhote, Nathan Lopez, Aliaume Schütze, Lia Formal Languages and Automata Theory 68Q45 F.4.3; F.4.2 The set of finite words over a well-quasi-ordered set is itself well-quasi-ordered. This seminal result by Higman is a cornerstone of the theory of well-quasi-orderings and has found numerous applications in computer science. However, this result is based on a specific choice of ordering on words, the (scattered) subword ordering. In this paper, we describe to what extent other natural orderings (prefix, suffix, and infix) on words can be used to derive Higman-like theorems. More specifically, we are interested in characterizing languages of words that are well-quasi-ordered under these orderings. We show that a simple characterization is possible for the prefix and suffix orderings, and that under extra regularity assumptions, this also extends to the infix ordering. We furthermore provide decision procedures for a large class of languages, that contains regular and context-free languages. |
| title | Well-Quasi-Orderings on Word Languages |
| topic | Formal Languages and Automata Theory 68Q45 F.4.3; F.4.2 |
| url | https://arxiv.org/abs/2501.07428 |