Deciding Conjugacy of a Rational Relation

A relation on the free monoid is conjugate if each pair of words in the relation is conjugate, i.e., cyclic shifts of each other. We show that checking whether a rational relation is conjugate is decidable. This extended abstract outlines the proof of this fact. A result of independent interest is a generalisation of the classical Lyndon-Schützenberger theorem from word combinatorics that equates conjugacy of a pair of words (u, v) and the existence of a word z (called a witness) such that \(uz=zv\) . A full version of the paper, with details of the proof, can be found on arXiv [1].