Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

An iterated uniform finite-state transducer (IUFST) runs the samelength-preserving transduction, starting with a sweep on the input string andthen iteratively sweeping on the output of the previous sweep. The IUFSTaccepts the input string by halting in an accepting state at the end of asweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST)version of this device. We show that constant sweep bounded IUFSTs and NIUFSTsaccept all and only regular languages. We study the state complexity ofremoving nondeterminism as well as sweeps on constant sweep bounded NIUFSTs,the descriptional power of constant sweep bounded IUFSTs and NIUFSTs withrespect to classical models of finite-state automata, and the computationalcomplexity of several decidability questions. Then, we focus on non-constantsweep bounded devices, proving the existence of a proper infinite nonregularlanguage hierarchy depending on the sweep complexity both in the deterministicand nondeterministic case. Though NIUFSTss are "one-way" devices we show thatthey characterize the class of context-sensitive languages, that is, thecomplexity class DSpace(lin). Finally, we show that the nondeterministicdevices are more powerful than their deterministic variant for a sublinearnumber of sweeps that is at least logarithmic