IRIS Institutional Research Information System - AIR Archivio Istituzionale della Ricerca
IRIS è il sistema di gestione integrata dei dati della ricerca (persone, progetti, pubblicazioni, attività) adottato dall'Università degli Studi di Milano.
AIR nasce in UNIMI nel 2006 con lo scopo di raccogliere, documentare e conservare le informazioni sulla produzione scientifica dell'Università degli Studi di Milano e costituisce di fatto l'Anagrafe della ricerca dell'Ateneo.
EnglishAn 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.
| Titolo: | Iterated Uniform Finite-State Transducers: Descriptional Complexity of Nondeterminism and Two-Way Motion | |
| Autori: | ||
| Parole Chiave: | Iterated transducers; Nondeterminism; Two-way motion | |
| Settore Scientifico Disciplinare: | Settore INF/01 - Informatica | |
| Data di pubblicazione: | 2020 | |
| Digital Object Identifier (DOI): | http://dx.doi.org/10.1007/978-3-030-62536-8_10 | |
| Tipologia: | Book Part (author) | |
| Appare nelle tipologie: | 03 - Contributo in volume |
File in questo prodotto:
| File | Descrizione | Tipologia | Licenza | |
|---|---|---|---|---|
| Kutrib2020_Chapter_IteratedUniformFinite-StateTra.pdf | Publisher's version/PDF | Administrator Richiedi una copia |
Pubblicazioni consigliate
Copyright © 2021