Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion

An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, that is, sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we first study devices that perform a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Moreover, the special case of unary languages is investigated, and a language family is presented that is immune to two-way motion and almost immune to nondeterminism, in the sense that these resources do not help in reducing the number of states and/or sweeps. Finally, we look at devices that perform a non-constant number of sweeps. Here, it turns out that in the deterministic case two-way motion is more powerful than one-way motion, whereas nondeterminism and one-way motion can be more powerful than determinism and two-way motion.