Complete Variable-Length Codes: An Excursion into Word Edit Operations
Jean Néraud · Lecture notes in computer science · 2020
Given an alphabet A and a binary relation $$\tau \subseteq A^*\times A^*$$ , a language $$X\subseteq A^*$$ is $$\tau $$ -independent if $$ \tau (X)\cap X\,=\,\emptyset $$ ; X is $$\tau $$ -closed if $$\tau (X)\subseteq 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 $$\mathcal{F}$$ containing X, X is maximal in $$\mathcal{F}$$ if no other set of $$\mathcal{F}$$ can strictly contain X. A language $$X\subseteq 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 $$\tau $$ -independent or $$\tau $$ -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.