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

Given an alphabet A and a binary relation [Formula: see text], a language [Formula: see text] is [Formula: see text]-independent if [Formula: see text]; X is [Formula: see text]-closed if [Formula: see text]. 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 [Formula: see text] containing X, X is maximal in [Formula: see text] if no other set of [Formula: see text] can strictly contain X. A language [Formula: see text] 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 [Formula: see text]-independent or [Formula: see text]-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.