@INPROCEEDINGS {10175685,
author = { Colcombet, Thomas and Doueneau-Tabot, Gaetan and Lopez, Aliaume },
booktitle = { 2023 38th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS) },
title = {{ ℤ-polyregular functions }},
year = {2023},
volume = {},
ISSN = {},
pages = {1-13},
abstract = { This paper studies a robust class of functions from finite words to integers that we call ℤ-polyregular functions. We show that it admits natural characterizations in terms of logics, ℤ-rational expressions, ℤ-rational series and transducers.We then study two subclass membership problems. First, we show that the asymptotic growth rate of a function is computable, and corresponds to the minimal number of variables required to represent it using logical formulas. Second, we show that first-order definability of ℤ-polyregular functions is decidable. To show the latter, we introduce an original notion of residual transducer, and provide a semantic characterization based on aperiodicity. },
keywords = {Computer science;Transducers;Semantics},
doi = {10.1109/LICS56636.2023.10175685},
url = {https://doi.ieeecomputersociety.org/10.1109/LICS56636.2023.10175685},
publisher = {IEEE Computer Society},
address = {Los Alamitos, CA, USA},
month =Jun}