Conjugacy of finite biprefix codes
Two languages X and Y are called conjugates, if they satisfy the conjugacy equation XZ = ZY for some non-empty language Z. We will compare solutions of this equation with those of the corresponding equation of words and study the case of finite biprefix codes X and Y. We show that the maximal Z in this case is rational. We will also characterize X and Y in the case where they are both finite biprefix codes. This yields the decidability of the conjugacy of two finite biprefix codes. (C) 2009 Elsevier B.V. All rights reserved.
conjugacy biprefix code language equation