Gray Cycles of Maximum Length Related to k-Character Substitutions
Résumé
Given a word binary relation τ we define a τ-Gray cycle over a finite language X to be a permutation w [i] 0≤i≤|X|−1 of X such that each word wi is an image of the previous word wi−1 by τ. In that framework, we introduce the complexity measure λ(n), equal to the largest cardinality of a language X having words of length at most n, and such that a τ-Gray cycle over X exists. The present paper is concerned with the relation τ = σ k , the so-called k-character substitution, where (u, v) belongs to σ k if, and only if, the Hamming distance of u and v is k. We compute the bound λ(n) for all cases of the alphabet cardinality and the argument n.
Origine : Fichiers produits par l'(les) auteur(s)