2026-07-23T05:16:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:22892 2025-10-02T13:36:41Z ddc:004 open_access

Commutative ℕ-Rational Series of Polynomial Growth Lopez, Aliaume Rational series weighted automata polyregular function commutative This paper studies which functions computed by ℤ-weighted automata can be realised 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Aliaume Lopez 2025 Is Part Of LIPIcs, Volume 327, 42nd International Symposium on Theoretical Aspects of Computer Science (STACS 2025) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2025.67 urn:nbn:de:0030-drops-228924 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2025.67 eng https://creativecommons.org/licenses/by/4.0/legalcode