Topologies for Error-Detecting Variable-Length Codes

Abstract

Given a finite alphabet $A$, a quasi-metric $d$ over $A^{\ast }$, and a non-negative integer $k$, we introduce the relation ${\tau }_{d,k}\subseteq A^{\ast }\times A^{\ast }$ such that $(x,y)\in {\tau }_{d,k}$ holds whenever $d(x,y)\le k$. The error detection capability of variable-length codes is expressed in term of conditions over ${\tau }_{d,k}$. With respect to the prefix metric, the factor one, and any quasi-metric associated with some free monoid (anti-)automorphism, we prove that one can decide whether a given regular variable-length code satisfies any of those error detection constraints.

arXiv admin note: text overlap with arXiv:2208.14681