Download PDFOpen PDF in browserComplete Variable-Length 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 T-independent if T(X)⋂X=Ø; X is T-closed 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 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 T-independent or T-closed variable-length 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, variable-length code, word
|