When Variable-Length Codes Meet the Field of Error Detection

Abstract

Given a finite alphabet A and a binary relation A^* A^*, a set X is - independent if (X) X=. Given a quasi-metric d over A^* (in the meaning of W31) and k 1, we associate the relation _d,k defined by (x,y)_d,k if, and only if, d(x,y) k CP02.In the spirit of JK97,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.

Tasks

Reproductions