When Variable-Length Codes Meet the Field of Error Detection

Given a finite alphabet A and a binary relation τsubseteq A^*× A^*, a set X is τ-it independent if τ(X)cap X=emptyset. Given a quasi-metric d over A^* (in the meaning of citeW31) and k≥ 1, we associate the relation τd,k defined by (x,y)∈τd,k if, and only if, d(x,y)≤ k citeCP02.In the spirit of citeJK97,N21, the error detection-correction capability of variable-length codes can be expressed in term of conditions over τ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.