10.46298/fi-2022-9638
https://fi.episciences.org/9638
Kutrib, Martin
Martin
Kutrib
Malcher, Andreas
Andreas
Malcher
Mereghetti, Carlo
Carlo
Mereghetti
Palano, Beatrice
Beatrice
Palano
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers
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.
episciences.org
Computer Science - Formal Languages and Automata Theory
2022-06-01
2022-07-07
2022-07-07
eng
journal article
arXiv:2205.15631
10.48550/arXiv.2205.15631
1875-8681
https://fi.episciences.org/9638/pdf
VoR
application/pdf
Fundamenta Informaticae
Volume 185, Issue 4
Researchers
Students