A deterministic iterated uniform finite-state transducer (for short, iufst) operates the same length-preserving transduction on several left-to-right sweeps. The first sweep occurs on the input string, while any other sweep processes the output of the previous one. We focus on constant sweep bounded iufsts. We study their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. Then, we focus on non-constant sweep bounded iufsts, showing a nonregular language hierarchy depending on sweep complexity.
Iterated uniform finite-state transducers / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano (CEUR WORKSHOP PROCEEDINGS). - In: ICTCS 2019 : 20th Italian Conference on Theoretical Computer Science / [a cura di] A. Cherubini, N. Sabadini, S. Tini. - [s.l] : CEUR-WS.org, 2019. - pp. 52-57 (( Intervento presentato al 20. convegno Italian Conference on Theoretical Computer Science tenutosi a Como nel 2019.
Iterated uniform finite-state transducers
C. Mereghetti;B. Palano
2019
Abstract
A deterministic iterated uniform finite-state transducer (for short, iufst) operates the same length-preserving transduction on several left-to-right sweeps. The first sweep occurs on the input string, while any other sweep processes the output of the previous one. We focus on constant sweep bounded iufsts. We study their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. Then, we focus on non-constant sweep bounded iufsts, showing a nonregular language hierarchy depending on sweep complexity.
| File | Dimensione | Formato | |
|---|---|---|---|
|
paper6.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
299.47 kB
Formato
Adobe PDF
|
299.47 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
