Commutative N-polyregular functions

A Lopez - arXiv preprint arXiv:2404.02232, 2024 - arxiv.org
A Lopez
arXiv preprint arXiv:2404.02232, 2024arxiv.org
This paper addresses two questions regarding N-polyregular functions, that forms a proper
subset of N-rational series. We show that given a Z-rational series, it is decidable whether it
is computable via a commutative N-polyregular function, and provide a counter-example to
the theorem of Karhum\" aki that studied the same question in the case of polynomials. We
also prove that it is decidable whether a commutative N-polyregular function is star-free, by
proving the stronger statement that star-free Z-polyregular functions that are N-polyregular …
This paper addresses two questions regarding N-polyregular functions, that forms a proper subset of N-rational series. We show that given a Z-rational series, it is decidable whether it is computable via a commutative N-polyregular function, and provide a counter-example to the theorem of Karhum\"aki that studied the same question in the case of polynomials. We also prove that it is decidable whether a commutative N-polyregular function is star-free, by proving the stronger statement that star-free Z-polyregular functions that are N-polyregular are in fact computable using a star-free N-polyregular function. Building towards answering the same questions in the non-commutative case, we present a canonical model of computation of N-polyregular functions by generalizing the notion of residual transducers previously introduced in Z-polyregular functions.
arxiv.org