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

Article type: Research Article

Authors: Kutrib, Martin^{; †} | Malcher, Andreas | Mereghetti, Carlo | Palano, Beatrice

Affiliations: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany. [email protected], [email protected] | Dip. di Informatica “G. degli Antoni”, Università degli Studi di Milano, via Celoria 18, 20133 Milano, Italy. [email protected], [email protected]

Correspondence: [†] Address of correspondence: Institut für Informatik, Universität Giessen, Arndtstr. 2, 35392 Giessen, Germany.

Note: [*] A preliminary version of this work was presented at the 16th Conference on Computability in Europe (CiE 2020), Fisciano, Italy, June 29th – July 2nd, 2020, and it is published in [1].

Abstract: An iterated uniform finite-state transducer (IUFST) runs 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 IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, 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. Though NIUFSTs are “one-way” devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace(lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.

Keywords: Iterated transducers, nondeterminism, descriptional complexity, sweep complexity, language hierarchies

DOI: 10.3233/FI-222113

Journal: Fundamenta Informaticae, vol. 185, no. 4, pp. 337-356, 2022