Journal article

Iterated uniform finite-state transducers on unary languages


Authors listKutrib, Martin; Malcher, Andreas; Mereghetti, Carlo; Palano, Beatrice

Publication year2023

JournalTheoretical Computer Science

Volume number969

ISSN0304-3975

eISSN1879-2294

Open access statusHybrid

DOI Linkhttps://doi.org/10.1016/j.tcs.2023.114049

PublisherElsevier


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 works on the output of the previous one. All sweeps always start from the sole initial state. The device accepts upon halting in an accepting state at the end of a sweep. We consider devices with one-way sweep motion and two-way sweep motion, i.e., sweeps are either from left to right only, or strictly alternate from left to right and from right to left. In addition, devices may work deterministically or nondeterministically. We focus on iterated uniform finite-state transducers accepting unary languages, i.e., languages built over single-letter alphabets.We show that any unary regular language can be accepted by a deterministic iterated uniform finite-state transducer with at most max{2 & BULL; & rho;, p} + 1 states, where p and p are the greatest primes in the factorization of the, respectively, pre-periodic and periodic part of the language. Such a state cost cannot be improved by using two-way motion, and it turns out to greatly outperform in the worst case the state costs of equivalent classical models of finite-state automata.Next, we give a characterization of classes of unary languages accepted by non-constant sweep-bounded iterated uniform finite-state transducers in terms of time-bounded one-way cellular automata. This characterization enables both to exhibit interesting families of unary nonregular languages accepted by iterated uniform finite-state transducers, and to prove the undecidability of several questions related to iterated uniform finite -state transducers accepting unary languages with an amount of sweeps that is at least logarithmic.& COPY; 2023 Elsevier B.V. All rights reserved.



Citation Styles

Harvard Citation styleKutrib, M., Malcher, A., Mereghetti, C. and Palano, B. (2023) Iterated uniform finite-state transducers on unary languages, Theoretical Computer Science, 969, Article 114049. https://doi.org/10.1016/j.tcs.2023.114049

APA Citation styleKutrib, M., Malcher, A., Mereghetti, C., & Palano, B. (2023). Iterated uniform finite-state transducers on unary languages. Theoretical Computer Science. 969, Article 114049. https://doi.org/10.1016/j.tcs.2023.114049



Keywords


AUTOMATACellular automataComplexityDESCRIPTIONAL COMPLEXITYIterated transducersPRIMESUnary languages

Last updated on 2025-10-06 at 11:55