Iterated Transduction on Unary Languages (short paper)

An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep processes the output of the previous one. We focus on unary inputs. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2arrho, p}+ 1 states, arrho and p being the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. This state cost cannot be improved by using nondeterminism, and is definitely lower than the state costs of equivalent classical models of finite-state automata.