Gray Cycles of Maximum Length Related to k-Character Substitutions

Given a word binary relation tau onto A* we define a tau-Gray cycle over a finite language X subset of A* to be a permutation (w([i]))(0 <= i <=vertical bar X vertical bar - 1) of X such that each word w(i) is an image of the previous word w(i-1) by tau. We introduce the complexity measure lambda(n), equal to the largest cardinality of a language X having words of length at most n, and such that some tau-Gray cycle over X exists. The present paper is concerned with the relation tau = sigma(k), the so-called k-character substitution, such that (u, v) belongs to sigma(k) if, and( )only if, the Hamming distance of u and v is k. We compute the bound lambda(n) for all cases of the alphabet cardinality and the argument n.