Comma-free Codes Over Finite Alphabets - Graphes, Algorithmes et Combinatoire Access content directly
Preprints, Working Papers, ... Year : 2019

Comma-free Codes Over Finite Alphabets

Abstract

Comma-free codes have been widely studied in the last sixty years, from points of view as diverse as biology, information theory and combinatorics. We develop new methods to study comma-free codes achieving the maximum size, given the cardinality of the alphabet and the length of the words. Specifically, we are interested in counting the number of such codes. We provide (two different proofs for) a closed-formula. The approach introduced is further developed to tackle well-known sub-families of comma-free codes, such as self-complementary and (generalisations of) non-overlapping codes. We also study codes that are not contained in strictly larger ones. For instance, we determine the maximal size of self-complementary comma-free codes and the number of codes reaching the bound. We provide a characterisation of-letter non-overlapping codes (over an alphabet of cardinality n), which allows us to devise the number of such codes that are not contained in any strictly larger one. Our approach mixes combinatorial and graph-theoretical arguments.
Fichier principal
Vignette du fichier
FMP+.pdf (509.64 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-02376793 , version 1 (22-11-2019)
hal-02376793 , version 2 (19-09-2023)

Identifiers

  • HAL Id : hal-02376793 , version 1

Cite

Elena Fimmel, Christian Michel, François Pirot, Jean-Sébastien Sereni, Lutz Strüngmann. Comma-free Codes Over Finite Alphabets. 2019. ⟨hal-02376793v1⟩
213 View
354 Download

Share

Gmail Facebook X LinkedIn More