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 processes the output of the previous one. We focus on unary inputs. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2arrho, p}+ 1 states, arrho and p being the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. This state cost cannot be improved by using nondeterminism, and is definitely lower than the state costs of equivalent classical models of finite-state automata.
Iterated Transduction on Unary Languages (short paper) / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano (CEUR WORKSHOP PROCEEDINGS). - In: ICTCS 2021 : 22nd Italian Conference on Theoretical Computer Science / [a cura di] C.S. Coen, I. Salvo. - [s.l] : CEUR-WS, 2021. - pp. 87-92 (( Intervento presentato al 22. convegno Italian Conference on Theoretical Computer Science, ICTCS tenutosi a Bologna nel 2021.
Iterated Transduction on Unary Languages (short paper)
C. MereghettiPenultimo
;B. PalanoUltimo
2021
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 processes the output of the previous one. We focus on unary inputs. We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2arrho, p}+ 1 states, arrho and p being the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. This state cost cannot be improved by using nondeterminism, and is definitely lower than the state costs of equivalent classical models of finite-state automata.File | Dimensione | Formato | |
---|---|---|---|
paper7.pdf
accesso aperto
Tipologia:
Publisher's version/PDF
Dimensione
450.97 kB
Formato
Adobe PDF
|
450.97 kB | Adobe PDF | Visualizza/Apri |
Pubblicazioni consigliate
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.