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

摘要

Given an alphabet A and a binary relation т ⊆ A* x A*, a language X ⊆ A* is т-independent if т(X) ∩ X - Ø; X is т-closed if т(X) ⊆ 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 strictly contain X. A language X ⊆ 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.