$\mathbb{N}$-polyregular functions arise from well-quasi-orderings
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2024
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917774680391680 |
|---|---|
| author | Lopez, Aliaume |
| author_facet | Lopez, Aliaume |
| contents | A fundamental construction in formal language theory is the Myhill-Nerode congruence on words, whose finitedness characterizes regular language. This construction was generalized to functions from $Σ^*$ to $\mathbb{Z}$ by Colcombet, Douéneau-Tabot, and Lopez to characterize the class of so-called $\mathbb{Z}$-polyregular functions. In this paper, we relax the notion of equivalence relation to quasi-ordering in order to study the class of $\mathbb{N}$-polyregular functions, that plays the role of $\mathbb{Z}$-polyregular functions among functions from $Σ^*$ to $\mathbb{N}$. The analogue of having a finite index is then being a well-quasi-ordering. This provides a canonical object to describe $\mathbb{N}$-polyregular functions, together with a powerful new characterization of this class. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07882 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $\mathbb{N}$-polyregular functions arise from well-quasi-orderings Lopez, Aliaume Formal Languages and Automata Theory 03D05, 03B70, 68Q45, 68Q70 F.1.1; F.4.1; F.4.3 A fundamental construction in formal language theory is the Myhill-Nerode congruence on words, whose finitedness characterizes regular language. This construction was generalized to functions from $Σ^*$ to $\mathbb{Z}$ by Colcombet, Douéneau-Tabot, and Lopez to characterize the class of so-called $\mathbb{Z}$-polyregular functions. In this paper, we relax the notion of equivalence relation to quasi-ordering in order to study the class of $\mathbb{N}$-polyregular functions, that plays the role of $\mathbb{Z}$-polyregular functions among functions from $Σ^*$ to $\mathbb{N}$. The analogue of having a finite index is then being a well-quasi-ordering. This provides a canonical object to describe $\mathbb{N}$-polyregular functions, together with a powerful new characterization of this class. |
| title | $\mathbb{N}$-polyregular functions arise from well-quasi-orderings |
| topic | Formal Languages and Automata Theory 03D05, 03B70, 68Q45, 68Q70 F.1.1; F.4.1; F.4.3 |
| url | https://arxiv.org/abs/2409.07882 |