Deterministic and Nondeterministic Iterated Uniform Finite-State Transducers: Computational and Descriptional Power

An iterated uniform finite-state transducer (IUFSTIUFST) operates the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFSTIUFST accepts or rejects the input string by halting in an accepting or rejecting state along its sweeps. We consider both the deterministic (IUFSTIUFST) and nondeterministic (NIUFSTNIUFST) version of this device. We show that constant sweep bounded IUFSTIUFSTs and NIUFSTNIUFSTs accept all and only regular languages. We study the size cost of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTNIUFSTs, and the descriptional power of constant sweep bounded IUFSTIUFSTs and NIUFSTNIUFSTs with respect to classical models of finite-state automata. Finally, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Also, we show that the nondeterministic devices are always more powerful than their deterministic variant if at least a logarithmic number of sweeps is given.