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

EasyChair Preprint 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: Variable Length, 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 code, word

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