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

An iterated uniform finite-state transducer ([Formula: see text]) 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 [Formula: see text] accepts or rejects the input string by halting in an accepting or rejecting state along its sweeps. We consider both the deterministic ([Formula: see text]) and nondeterministic ([Formula: see text]) version of this device. We show that constant sweep bounded [Formula: see text]s and [Formula: see text]s accept all and only regular languages. We study the size cost of removing nondeterminism as well as sweeps on constant sweep bounded [Formula: see text]s, and the descriptional power of constant sweep bounded [Formula: see text]s and [Formula: see text]s 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.