Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2009 | 10.1016/j.tcs.2009.02.030 | Theor. Comput. Sci. |
Keywords | DocType | Volume |
non-empty language,Language equation,finite biprefix code,finite biprefix codes X,Biprefix code,Conjugacy,languages X,corresponding equation,conjugacy equation,maximal Z | Journal | 410 |
Issue | ISSN | Citations |
24-25 | Theoretical Computer Science | 1 |
PageRank | References | Authors |
0.38 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Julien Cassaigne | 1 | 282 | 40.80 |
Juhani Karhumäki | 2 | 1115 | 152.77 |
Petri Salmela | 3 | 17 | 4.71 |