2022/08/31 by Néraud, Jean
#Computation and Language (cs.CL) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.2208.14681
Given a finite alphabet A and a binary relation τ⊆ A^*× A^*, a set X is τ-\it independent if τ(X)∩ X=∅. 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.