Martin Kutrib ; Andreas Malcher ; Carlo Mereghetti ; Beatrice Palano - Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

fi:9638 - Fundamenta Informaticae, July 7, 2022, Volume 185, Issue 4
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

Authors: Martin Kutrib ; Andreas Malcher ; Carlo Mereghetti ; Beatrice Palano

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 NIUFSTss 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.


Volume: Volume 185, Issue 4
Published on: July 7, 2022
Accepted on: June 1, 2022
Submitted on: June 1, 2022
Keywords: Computer Science - Formal Languages and Automata Theory


Share

Consultation statistics

This page has been seen 20 times.
This article's PDF has been downloaded 14 times.