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 TransducersArticle

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

    Consultation statistics

    This page has been seen 100 times.
    This article's PDF has been downloaded 80 times.