Preservation Theorems for Transducer Outputs
Provides theoretical guarantees for property preservation in transducer outputs, relevant to automata theory and symbolic dynamics.
The paper studies which combinatorial properties of infinite words (e.g., recurrence, being morphic, factor frequencies) are preserved under deterministic finite-state transducers, using the Krohn-Rhodes theorem and ergodic theory of shift spaces.
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.