Download PDFOpen PDF in browserComplete VariableLength Codes: An Excursion into Word Edit OperationsEasyChair Preprint no. 219512 pages•Date: December 18, 2019AbstractGiven an alphabet A and a binary relation T onto A*, a language X over A is Tindependent if T(X)⋂X=Ø; X is Tclosed if T(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, say P, containing X, X is maximal in P if no other set of P can strictly contain X. A language X⊆A* is a variablelength 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 Tindependent or Tclosed variablelength codes. We focuse to those binary relations by which the images of a given word are computed by deleting, inserting, or substituting some of its characters. Keyphrases: binary relation, character deletion, closed, closed code, closed set, code, complete, complete code, complete regular, complete variable length code, deletion, edit operation, embedding, finite alphabet, free monoid, independent code, insertion, k character deletion, k closed code, maximal, maximal code, non complete, non complete code, non complete k closed code, positive bernoulli distribution, regular, regular code, regular independent code, string, substitution, subword, uniform bernoulli distribution, Variable Length, variablelength code, word
