We introduce the deterministic computational model of an iterated uniform finite-state transducer (IUFST). An IUFST performs the same length-preserving transduction on several left-to-right sweeps. The first sweep acts on the input string, any other sweep processes the output of the previous one. The IUFST accepts by halting in an accepting state at the end of a sweep. First, we study constant sweep bounded IUFSTs. We prove their computational power coincides with the class of regular languages. We show their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. We prove the NL-completeness of typical decision problems. Next, we analyze non-constant sweep bounded IUFSTs. We show they can accept non-regular languages provided an at least logarithmic amount of sweeps is allowed. We exhibit a proper non-regular language hierarchy depending on sweep complexity. The non-semidecidability of typical decision problems is also addressed.

Descriptional complexity of iterated uniform finite-state transducers / M. Kutrib, A. Malcher, C. Mereghetti, B. Palano. - In: INFORMATION AND COMPUTATION. - ISSN 0890-5401. - (2021). [Epub ahead of print] [10.1016/j.ic.2021.104691]

Descriptional complexity of iterated uniform finite-state transducers

Mereghetti C.;Palano B.
2021

Abstract

We introduce the deterministic computational model of an iterated uniform finite-state transducer (IUFST). An IUFST performs the same length-preserving transduction on several left-to-right sweeps. The first sweep acts on the input string, any other sweep processes the output of the previous one. The IUFST accepts by halting in an accepting state at the end of a sweep. First, we study constant sweep bounded IUFSTs. We prove their computational power coincides with the class of regular languages. We show their descriptional power vs. deterministic finite automata, and the state cost of implementing language operations. We prove the NL-completeness of typical decision problems. Next, we analyze non-constant sweep bounded IUFSTs. We show they can accept non-regular languages provided an at least logarithmic amount of sweeps is allowed. We exhibit a proper non-regular language hierarchy depending on sweep complexity. The non-semidecidability of typical decision problems is also addressed.
Decidability; Iterated transducers; State complexity; Sweep complexity
Settore INF/01 - Informatica
6-gen-2021
INFORMATION AND COMPUTATION
Article (author)
File in questo prodotto:
File Dimensione Formato  
IN PRESS.pdf

non disponibili

600.04 kB Adobe PDF   Visualizza/Apri   Richiedi una copia
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/810930
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 1
  • ???jsp.display-item.citation.isi??? 1
social impact