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

EasyChair Preprint no. 2195

Abstract

Given 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

@Booklet{EasyChair:2195,
  author = {Jean Néraud},
  title = {Complete Variable-Length Codes: An Excursion into Word Edit Operations},
  howpublished = {EasyChair Preprint no. 2195},

  year = {EasyChair, 2019}}