2024/04/02 by Lopez, Aliaume · 1 citation
#11T06 #68Q45 #68Q70 #F.1.1 #F.4.3 #FOS: Computer and information sciences #Logic in Computer Science (cs.LO)
paper · doi:10.48550/arxiv.2404.02232
This paper studies which functions computed by ℤ-weighted automata can be realized by ℕ-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 ℕ-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 ℕ-weighted automata of polynomial growth based on the notion of residual transducer.