Can I read Commutative N-polyregular functions on EtoBox?

Commutative N-polyregular functions by Lopez, Aliaume is a scholarly article available to read on EtoBox.

What is Commutative N-polyregular functions about?

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.

Author

Lopez, Aliaume

Published

2024

Language

EN