Topologies for error-detecting variable-length codes

Given a finite alphabet A and a quasi-metric d over A ⁎, we introduce the relation τ d, k ⊆ A ⁎ × A ⁎ such that ( x, y ) ∈ τ d, k holds whenever d ( x, y ) ≤ k. The error detection capability of variable-length codes is expressed in term of conditions over τ 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.

Authors

• Jean Néraud

Keywords

• Automaton
• Code
• Error detection
• Independent
• Quasi-metric
• Word relation