Deciding Conjugacy of a Rational Relation

The conjugacy problem asks if a given pair of elements in a finitely presented monoid (typically infinite) is conjugate, i. e. , a cyclic shift of one another. Conjugacy problem over free monoids is solvable in polynomial time. We consider a generalisation of the problem to a finitely-presented possibly infinite set of pairs (or relation). A relation over the free monoid is conjugate if each pair of words in the relation is conjugate. We address the conjugacy problem of a relation. It is particularly interesting when the relation is automata-definable. We show that conjugacy of rational relations, those accepted by a finite state transducer, is decidable. Towards our decision procedure, we establish a new result that is of independent interest to word combinatorics. We identify a necessary and sufficient condition for the set of pairs given by (u_0, v_0)G_1*(u_1, v_1). .. G_k*(u_k, v_k), k > 0 to be conjugate, where G_1, .. ., G_k are arbitrary sets of pairs of words, and (u_0, v_0), .. ., (u_k, v_k) are arbitrary pairs of words. This is similar to, and a nontrivial generalisation of, a characterisation given by Lyndon and Schützenberger in 1962 for the conjugacy of a pair of words. Finally, we discuss towards conjugacy of regular relations, those accepted by a two-way finite state transducer. This is a joint work with C. Aiswarya (CMI) and Amaldev Manuel (IIT Goa). It is based on a paper accepted in DLT 2024. The full version of the paper can be found in arXiv ( https: //arxiv. org/abs/2307. 06777 ).

Authors

• Saina Sunny

Keywords

No keywords are indexed for this paper.