Complete variable-length codes: an excursion into word edit operations

DOI10.1007/978-3-030-40608-0_31MaRDI QIDQ782607zbMATH OpenOpenAlexFDO

Authors J. Néraud

Publication date 27 July 2020

Full work available at URL https://arxiv.org/abs/1912.02646

zbMATH Keywords

completenessstringvariable-length codemaximalitysubstringclosed languageword edit operations

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Prefix, length-variable, comma-free codes (94A45)

Abstract: Given an alphabet A and a binary relation $au$ $subseteq$ A * x A * , a language X $subseteq$ A * is $au$-independent if $au$ (X) $cap$ X = $emptyset$; X is $au$-closed if $au$ (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 $au$-independent or $au$-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.

Recommendations

• Variable-length codes independent or closed with respect to edit relations
• Complete variable-length ``fix-free codes
• Maximal and variable word-length comma-free codes
• Optimal variable-length insertion-deletion correcting codes and edit metric codes
• The Construction of Variable-length Comma-Free Codes
• Variable length codes and finite automata
• scientific article; zbMATH DE number 8125
• Comma free error correcting codes of variable length, generated by finite-state encoders
• Variable-length error-correcting codes based on finite automata
• On a class of efficient error-limiting variable-length codes

Cited in

(2)

• Variable-length codes independent or closed with respect to edit relations
• The second step in characterizing a three-word code

This page was built for publication: Complete variable-length codes: an excursion into word edit operations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782607)