# Complete Variable-Length Codes: An Excursion into Word Edit Operations

arXiv: https://arxiv.org/abs/1912.02646 · HTML: https://mlsanity.com/paper/1912.02646/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2019.

## Built on by (most cited first, 1 of 1)

- [Variable-Length Codes Independent or Closed with respect to Edit Relations](https://mlsanity.com/paper/2104.14185/) (2021)

## Abstract (arXiv)

Given an alphabet A and a binary relation τ subseteq A * x A * , a language X subseteq A * is τ-independent if τ (X) cap X = emptyset; X is τ-closed if τ (X) subseteq X. The language X is complete if any word over A is a factor of some concatenation of words in X. Given a family of languages F containing X, X is maximal in F if no other set of F can stricly contain X. A language X subseteq A * is a variable-length code if any equation among the words of X is necessarily trivial. The study discusses the relationship between maximality and completeness in the case of τ-independent or τ-closed variable-length codes. We focus to the binary relations by which the images of words are computed by deleting, inserting, or substituting some characters.