eng
episciences.org
Fundamenta Informaticae
0169-2968
1875-8681
2022-07-07
Volume 185, Issue 4
10.46298/fi-2022-9638
9638
journal article
Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers
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.
https://fi.episciences.org/9638/pdf
Computer Science - Formal Languages and Automata Theory