It is shown that, if X and Y are prefix codes and Z is a non-empty language satisfying the condition X Z = Z Y , then Z is the union of a non-empty family { P n } i ź I of pairwise disjoint prefix sets such that X P i = P i Y for all i ź I . Consequently, the conjugacy relations of prefix codes are explored and, under the restriction that both of X and Y are prefix codes, the solutions of the conjugacy equation X Z = Z Y for languages are determined. Also, the decidability of the conjugacy problem for finite prefix codes is confirmed.
['Yong He', 'Zhenhe Cui', 'Zihan Yuan']
Conjugacy relations of prefix codes