Preservation Theorems for Transducer Outputs
2026-06-29 • Formal Languages and Automata Theory
Formal Languages and Automata Theory
AI summaryⓘ
The authors explore what happens when a special kind of machine called a deterministic finite-state transducer transforms an infinite sequence of symbols into a new infinite sequence. They specifically look at which important patterns or properties of the original sequence still exist after the transformation. Using a famous mathematical tool called the Krohn-Rhodes theorem, along with ideas from ergodic theory and symbolic dynamics, they show how certain patterns like recurrence and frequency of factors are preserved. Their work helps us understand how complex transformations affect infinite sequences.
deterministic finite-state transducerinfinite wordrecurrencemorphic sequencefactor frequencyKrohn-Rhodes theoremergodic theorysymbolic dynamicsshift space
Authors
Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov, Dominique Perrin, Mihir Vahanwala
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.