Journalartikel

Jahr der Veröffentlichung: 2022

Zeitschrift: Information and Computation

Bandnummer: 284

ISSN: 0890-5401

eISSN: 1090-2651

Open Access Status: Green

DOI Link: https://doi.org/10.1016/j.ic.2021.104691

Verlag: Elsevier

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. (c) 2021 Elsevier Inc. All rights reserved.

Harvard-Zitierstil: Kutrib, M., Malcher, A., Mereghetti, C. and Palano, B. (2022) Descriptional complexity of iterated uniform finite-state transducers, Information and Computation, 284, Article 104691. https://doi.org/10.1016/j.ic.2021.104691

APA-Zitierstil: Kutrib, M., Malcher, A., Mereghetti, C., & Palano, B. (2022). Descriptional complexity of iterated uniform finite-state transducers. Information and Computation. 284, Article 104691. https://doi.org/10.1016/j.ic.2021.104691