When Variable-Length Codes Meet the Field of Error Detection

Abstract

Given a finite alphabet $A$ and a binary relation $\tau \subseteq A^{\ast }\times A^{\ast }$, a set $X$ is $\tau$-{\it independent} if $\tau (X)\cap X=\varnothing$. Given a quasi-metric $d$ over $A^{\ast }$ (in the meaning of \cite{W31}) and $k\ge 1$, we associate the relation ${\tau }_{d,k}$ defined by $(x,y)\in {\tau }_{d,k}$ if, and only if, $d(x,y)\le k$ \cite{CP02}.In the spirit of \cite{JK97,N21}, the error detection-correction capability of variable-length codes can be expressed in term of conditions over ${\tau }_{d,k}$. With respect to the prefix metric, the factor one, and every quasi-metric associated to (anti-)automorphisms of the free monoid, we examine whether those conditions are decidable for a given regular code.