Preservation Theorems for Transducer Outputs

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 talk, we
consider this preservation question for various well-known classes of
words having desirable combinatorial properties, e.g., recurrent words,
primitive morphic words, and words that admit 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. This talk is based on
joint work with Valérie Berthé, Herman Goulet-Ouellet, Toghrul Karimov,
and Dominique Perrin.

BIO
Mihir Vahanwala is a PhD candidate at MPI-SWS and Saarland Informatics
Campus. He is primarily interested in solving theoretical
computer-scientific problems that lie at the intersection of dynamical
systems, number theory, and logic. His work has been recognised with the
Distinguished Paper Award at LICS 2024.