An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are 'one-way' devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace(lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano. - In: FUNDAMENTA INFORMATICAE. - ISSN 0169-2968. - 185:4(2022 Jun 21), pp. 337-356. [10.3233/FI-222113]

Computational and Descriptional Power of Nondeterministic Iterated Uniform Finite-State Transducers

C. Mereghetti
Penultimo
;
B. Palano
Ultimo
2022-06-21

Abstract

An iterated uniform finite-state transducer (IUFST) runs the same length-preserving transduction, starting with a sweep on the input string and then iteratively sweeping on the output of the previous sweep. The IUFST accepts the input string by halting in an accepting state at the end of a sweep. We consider both the deterministic (IUFST) and nondeterministic (NIUFST) version of this device. We show that constant sweep bounded IUFSTs and NIUFSTs accept all and only regular languages. We study the state complexity of removing nondeterminism as well as sweeps on constant sweep bounded NIUFSTs, the descriptional power of constant sweep bounded IUFSTs and NIUFSTs with respect to classical models of finite-state automata, and the computational complexity of several decidability questions. Then, we focus on non-constant sweep bounded devices, proving the existence of a proper infinite nonregular language hierarchy depending on the sweep complexity both in the deterministic and nondeterministic case. Though NIUFSTs are 'one-way' devices we show that they characterize the class of context-sensitive languages, that is, the complexity class DSpace(lin). Finally, we show that the nondeterministic devices are more powerful than their deterministic variant for a sublinear number of sweeps that is at least logarithmic.
descriptional complexity; Iterated transducers; language hierarchies; nondeterminism; sweep complexity;
Settore INF/01 - Informatica
Article (author)
File in questo prodotto:
File Dimensione Formato  
pubblicato.pdf

accesso riservato

Tipologia: Publisher's version/PDF
Dimensione 271.15 kB
Formato Adobe PDF
271.15 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
2205.15631.pdf

accesso aperto

Tipologia: Pre-print (manoscritto inviato all'editore)
Dimensione 215.82 kB
Formato Adobe PDF
215.82 kB Adobe PDF Visualizza/Apri
Pubblicazioni consigliate

Caricamento pubblicazioni consigliate

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/2434/937058
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 0
  • ???jsp.display-item.citation.isi??? ND
social impact