Journal article

Publication year: 2022

Journal: Information and Computation

Volume number: 284

ISSN: 0890-5401

eISSN: 1090-2651

Open access status: Green

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

Publisher: 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 Citation style: 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 Citation style: 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