Commutative N-polyregular functions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909914590347264 |
|---|---|
| author | Lopez, Aliaume |
| author_facet | Lopez, Aliaume |
| contents | This paper studies which functions computed by $\mathbb{Z}$-weighted automata can be realized by $\mathbb{N}$-weighted automata, under two extra assumptions: commutativity (the order of letters in the input does not matter) and polynomial growth (the output of the function is bounded by a polynomial in the size of the input). We leverage this effective characterization to decide whether a function computed by a commutative $\mathbb{N}$-weighted automaton of polynomial growth is star-free, a notion borrowed from the theory of regular languages that has been the subject of many investigations in the context of string-to-string functions during the last decade. Furthermore, we open the road to a generalization of our results to non-commutative functions, by formalizing a canonical computational model for $\mathbb{N}$-weighted automata of polynomial growth based on the notion of residual transducer. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_02232 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Commutative N-polyregular functions Lopez, Aliaume Logic in Computer Science 11T06, 68Q45, 68Q70 F.1.1; F.4.3 This paper studies which functions computed by $\mathbb{Z}$-weighted automata can be realized by $\mathbb{N}$-weighted automata, under two extra assumptions: commutativity (the order of letters in the input does not matter) and polynomial growth (the output of the function is bounded by a polynomial in the size of the input). We leverage this effective characterization to decide whether a function computed by a commutative $\mathbb{N}$-weighted automaton of polynomial growth is star-free, a notion borrowed from the theory of regular languages that has been the subject of many investigations in the context of string-to-string functions during the last decade. Furthermore, we open the road to a generalization of our results to non-commutative functions, by formalizing a canonical computational model for $\mathbb{N}$-weighted automata of polynomial growth based on the notion of residual transducer. |
| title | Commutative N-polyregular functions |
| topic | Logic in Computer Science 11T06, 68Q45, 68Q70 F.1.1; F.4.3 |
| url | https://arxiv.org/abs/2404.02232 |