  A rational relation is conjugate if every pair of words in the relation are
conjugates, i.e., cyclic shifts of each other. We show that checking whether a
rational relation is conjugate is decidable.
  We assume that the rational relation is given as a rational expression over
pairs of words. Every rational expression is effectively equivalent to a sum of
sumfree expressions, possibly with an exponential size blow-up. Hence, the
general problem reduces to determining the conjugacy of sumfree rational
expressions. To solve this specific case, we give two generalisations of the
Lyndon-Sch\"utzenberger's 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 set of conjugate pairs has a common witness if
there is a word that is a witness for every pair in the set. We show the
following.
  1. If $G$ is an arbitrary set of conjugate pairs, then $G^*$ is conjugate if
and only if there is a common witness for $G$.
  2. If $G_1^*, \ldots, G_k^*, k > 0$, be arbitrary sets of conjugate pairs and
$(a_0, b_0), \ldots, (a_k, b_k)$ be arbitrary pairs of words, then the set of
words \[G = (a_0, b_0) G_1^* (a_1, b_1) \cdots G_k^*(a_k,b_k)\] is conjugate if
and only if it has a common witness.
  A consequence is that a set of pairs generated by a sumfree rational
expression is conjugate if and only if there is a word witnessing the conjugacy
of all the pairs. Moreover the witness is effectively computable leading to an
algorithm to decide the conjugacy.
