An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, i.e., sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we restrict to study devices performing a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Finally, the special case of unary languages is investigated, and a language family is presented that is immune to the resources of nondeterminism and two-way motion, in the sense that both resources can neither reduce the number of states nor the number of sweeps.
Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: Descriptional Complexity of Formal Systems / [a cura di] G. Jirásková, G. Pighizzini. - [s.l] : Springer, 2020. - ISBN 9783030625351. - pp. 117-129 (( Intervento presentato al 22. convegno Descriptional Complexity of Formal Systems (DCFS) tenutosi a Wien nel 2020 [10.1007/978-3-030-62536-8_10].
Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion
C. Mereghetti;B. Palano
2020
Abstract
An iterated uniform finite-state transducer executes the same length-preserving transduction in iterative sweeps. The first sweep occurs on the input string, while any subsequent sweep works on the output of the previous one. We consider devices with one-way motion and two-way motion, i.e., sweeps are either from left to right only, or alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. Here, we restrict to study devices performing a constant number of sweeps, which are known to characterize exactly the regular languages. We determine the descriptional costs of removing two-way motion, nondeterminism, and sweeps, and, in particular, the costs for the conversion to deterministic or nondeterministic finite automata. Finally, the special case of unary languages is investigated, and a language family is presented that is immune to the resources of nondeterminism and two-way motion, in the sense that both resources can neither reduce the number of states nor the number of sweeps.File | Dimensione | Formato | |
---|---|---|---|
Kutrib2020_Chapter_IteratedUniformFinite-StateTra.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
310.12 kB
Formato
Adobe PDF
|
310.12 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.