When variable-length codes meet the field of error detection

DOI10.1007/978-3-031-19685-0_15MaRDI QIDQ6108733zbMATH OpenOpenAlexFDO

Authors J. Néraud

Publication date 26 July 2023

Published in Algebraic Informatics (Search for Journal in Brave)

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

zbMATH Keywords

anti-automorphismanti-reflexiveautomatonautomorphismBernoulli measurebinary relationchannelcodecodewordcompletedistanceembeddingerror correctionerror detectionfactorfree monoidhomomorphismindependentinput wordKraft inequalitymaximalmeasuremetricmonoidoutput wordprefixquasi-metricregularsubsequencessuffixsynchronization constrainttransducervariable-length codeword

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Abstract: Given a finite alphabet $A$ and a binary relation $ausubseteq{A}^{\ast }imes{A}^{\ast }$, a set $X$ is $au$-{it independent} if $au(X)capX=emptyset$. Given a quasi-metric $d$ over $A^{\ast }$ (in the meaning of cite{W31}) and $kge1$, we associate the relation $a{u}_{d,k}$ defined by $(x,y)ina{u}_{d,k}$ if, and only if, $d(x,y)lek$ cite{CP02}.In the spirit of cite{JK97,N21}, the error detection-correction capability of variable-length codes can be expressed in term of conditions over $a{u}_{d,k}$. With respect to the prefix metric, the factor one, and every quasi-metric associated to (anti-)automorphisms of the free monoid, we examine whether those conditions are decidable for a given regular code.

Cites work

• An Overview of Sequence Comparison: Time Warps, String Edits, and Macromolecules
• Codes and automata.
• Completing circular codes in regular submonoids
• Completing comma-free codes
• Completion of recognizable bifix codes
• Distances between languages and reflexivity of relations
• Each regular code is included in a maximal regular code
• Elements of automata theory. Translated from the French by Reuben Thomas
• Embedding a -invariant code into a complete one
• Embedding rationally independent languages into maximal ones
• Error detecting and error correcting codes
• Finite maximal infix codes
• Finite maximal solid codes
• scientific article; zbMATH DE number 5117090 (Why is no real title available?)
• scientific article; zbMATH DE number 3720983 (Why is no real title available?)
• scientific article; zbMATH DE number 3497806 (Why is no real title available?)
• scientific article; zbMATH DE number 941396 (Why is no real title available?)
• scientific article; zbMATH DE number 3240929 (Why is no real title available?)
• Maximal solid codes
• On codes having no finite completions
• On completion of codes with finite deciphering delay
• On Quasi-Metric Spaces
• On Relations Defined by Generalized Finite Automata
• On the maximality of languages with combined types of code properties
• Prefix distance between regular languages
• Theoretical Aspects of Computing – ICTAC 2005
• Variable-length codes independent or closed with respect to edit relations

Cited in

(5)

• A Comparison of Some Error Detecting CRC Code Standards
• On a class of efficient error-limiting variable-length codes
• Constructions for variable-length error-correcting codes
• Loopless algorithms to generate maximum length Gray cycles wrt. \(k\)-character substitutions
• Topologies for error-detecting variable-length codes

This page was built for publication: When variable-length codes meet the field of error detection

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