Conjugacy of finite biprefix codes

Two languages X and Y are called conjugates, if they satisfy the conjugacy equation X Z = Z Y 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...

Full description

Saved in:
Bibliographic Details
Published in:Theoretical computer science 2009-05, Vol.410 (24), p.2345-2351
Main Authors: Cassaigne, Julien, Karhumäki, Juhani, Salmela, Petri
Format: Article
Language:English
Subjects:
Biprefix code
Conjugacy
Language equation
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Two languages X and Y are called conjugates, if they satisfy the conjugacy equation X Z = Z Y 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.
ISSN:0304-3975
1879-2294
DOI:10.1016/j.tcs.2009.02.030