Preservation Theorems for Transducer Outputs

2026/06/29 by Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov +2 · 1 voice
Computer Science · #cs.FL

paper · pdf

Abstract

Suppose we have a deterministic finite-state transducer A and an infinite word x, and run A on x to obtain an infinite word A(x). Which properties of x are guaranteed to also hold for A(x)? In this paper, we study this preservation question for various well-known combinatorial properties, e.g., recurrence, being morphic, and having factor frequencies. The celebrated Krohn-Rhodes theorem provides the framework for proving our preservation results, and our techniques are based on the ergodic theory of symbolic dynamical systems, i.e., shift spaces.

Citations

• Stability properties for subgroups generated by return words
• The Monadic Theory of Toric Words
• Preservation of normality by unambiguous transducers
• Preservation of normality by transducers
• Beyond substitutive dynamical systems: S-adic expansions
• Decidability of uniform recurrence of morphic sequences
• Decidability of the HD0L ultimate periodicity problem
• Skew products over rotations with exotic properties
• Episturmian words: a survey
• A Condition of Boshernitzan and Uniform Convergence in the Multiplicative Ergodic Theorem
• What is Aperiodic Order?
• What is Aperiodic Order?
• Substitutional dynamical systems, Bratteli diagrams and dimension groups

Discussions

• Val\'erie Berth\'e, Herman Goulet-Ouellet, Toghrul Karimov, Dominique Perrin, Mihir Vahanwala: Preservation Theorems for Transducer Outputs https://arxiv.org/abs/2606.30013 https://arxiv.org/pdf/2606. [bsky, 0 points, 0 comments]

Related

• Preservation of normality by transducers
• Preservation of normality by unambiguous transducers
• From Two-Way to One-Way Finite State Transducers
• Reversible Transducers over Infinite Words
• Approximate Problems for Finite Transducers