Rational relations are precisely those relations on words that are definable by transducers, i.e., automata with output. Two words are conjugate if they are cyclic shifts of each other, or equivalently, of the form xy and yx for some words x and y. The conjugacy problem for rational relations asks if a given rational relation is conjugate. We show that the problem is decidable in exponential time (and polytime for sumfree rational expressions). The proof relies on a generalisation of a classic theorem by Lyndon-Schützenberger from word combinatorics. In the talk, we will discuss some historic applications of the conjugacy problem, our particular motivation to study the problem, and a brief sketch of the proof. Joint work with C. Aiswarya (CMI) and Saina Sunny (IIT GOA)
A draft of the paper is available at: https://arxiv.org/abs/2307.06777
