We consider the model of an iterated uniform finite-state transducer, which executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of the previous one. We focus on unary languages. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2⋅ϱ,p}+1max{2⋅ϱ,p}+1 states, where ϱϱ and p are the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. Such a state cost cannot be improved by using nondeterminism, and it turns out to be exponentially lower in the worst case than the state costs of equivalent classical models of finite-state automata. Next, we give a characterization of classes of unary languages accepted by non-constant sweep-bounded iterated uniform finite-state transducers in terms of time bounded one-way cellular automata. This characterization enables both to exhibit interesting families of unary non-regular languages accepted by iterated uniform finite-state transducers, and to prove the undecidability of several questions related to iterated uniform finite-state transducers accepting unary languages with an amount of sweeps that is at least logarithmic.
Iterated Uniform Finite-State Transducers on Unary Languages / M. Kutrib, A. Malcher, C. Mereghetti, B.S. Palano (LECTURE NOTES IN ARTIFICIAL INTELLIGENCE). - In: SOFSEM 2021: Theory and Practice of Computer Science / [a cura di] T. Bureš, R. Dondi, J. Gamper, G. Guerrini, T. Jurdziński, C. Pahl, F. Sikora, P.W.H. Wong. - [s.l] : Springer, 2021. - ISBN 9783030677305. - pp. 218-232 (( Intervento presentato al 47. convegno International Conference on Current Trends in Theory and Practice of Computer Science tenutosi a Bolzano nel 2021 [10.1007/978-3-030-67731-2_16].
Iterated Uniform Finite-State Transducers on Unary Languages
C. Mereghetti
Penultimo
;B.S. Palano
Ultimo
2021
Abstract
We consider the model of an iterated uniform finite-state transducer, which executes the same length-preserving transduction in iterative sweeps. The first sweep takes place on the input string, while any subsequent sweep works on the output of the previous one. We focus on unary languages. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2⋅ϱ,p}+1max{2⋅ϱ,p}+1 states, where ϱϱ and p are the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. Such a state cost cannot be improved by using nondeterminism, and it turns out to be exponentially lower in the worst case than the state costs of equivalent classical models of finite-state automata. Next, we give a characterization of classes of unary languages accepted by non-constant sweep-bounded iterated uniform finite-state transducers in terms of time bounded one-way cellular automata. This characterization enables both to exhibit interesting families of unary non-regular languages accepted by iterated uniform finite-state transducers, and to prove the undecidability of several questions related to iterated uniform finite-state transducers accepting unary languages with an amount of sweeps that is at least logarithmic.File | Dimensione | Formato | |
---|---|---|---|
sofsem-final.pdf
accesso riservato
Tipologia:
Post-print, accepted manuscript ecc. (versione accettata dall'editore)
Dimensione
320.93 kB
Formato
Adobe PDF
|
320.93 kB | Adobe PDF | Visualizza/Apri Richiedi una copia |
Kutrib2021_Chapter_IteratedUniformFinite-StateTra.pdf
accesso riservato
Tipologia:
Publisher's version/PDF
Dimensione
383.01 kB
Formato
Adobe PDF
|
383.01 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.