$\mathbbN$-polyregular functions arise from well-quasi-orderings
<|reference_start|>$\mathbbN$-polyregular functions arise from well-quasi-orderings: 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 $\Sigma^*$ to $\mathbb{Z}$ by Colcombet, Dou\'eneau-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 $\Sigma^*$ 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.<|reference_end|>
@article{lopez2024$\mathbb{n}$-polyregular,
    title={$\mathbb{N}$-polyregular functions arise from well-quasi-orderings},
    author={Aliaume Lopez},
    journal={arXiv preprint arXiv:2409.07882},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.07882},
    primaryClass={cs.FL}
}