Complete Variable-Length Codes: An Excursion into Word Edit Operations
This work addresses a theoretical problem in formal language theory for researchers studying coding and combinatorics on words, but it appears incremental as it extends known concepts to specific edit operations.
The paper investigates the relationship between maximality and completeness for variable-length codes under word edit operations like deletion, insertion, and substitution, establishing theoretical conditions for when such codes achieve these properties.
Given an alphabet A and a binary relation $τ$ $\subseteq$ A * x A * , a language X $\subseteq$ A * is $τ$-independent if $τ$ (X) $\cap$ X = $\emptyset$; X is $τ$-closed if $τ$ (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 F containing X, X is maximal in F if no other set of F can stricly 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 $τ$-independent or $τ$-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.