Biprefix code and word factorization

46 Views Asked by At

Let $Y_1$ a biprefix code over a free monoid $A^{*}$. Let $u= x_{i}y_{j}$ and $v= x_{i}’y_{j}’$, with $x_i, x_i’ \in A^*$ and $y_j, y_j’ \in Y_1$. If $u=v$, while does this imply that $y_{i} = y_{i}’$?

1

There are 1 best solutions below

2
On BEST ANSWER

A biprefix code is in particular a suffix code. Now $u = v$ implies that either $y_j$ is a suffix of $y'_j$ or that $y_j$ is a suffix of $y'_j$. Since your code is suffix, this implies $y_j = y'_j$.

EDIT (Answer to your comment). Would this picture help you?

Suffix