Loopless algorithms to generate maximum length gray cycles wrt. k-character substitutions

Given a binary word relation tau onto A* and a finite language X c A* , a tau-Gray cycle over X consists in a permutation (w[i])0 <= i <=|X|-1 of X such that each word w[i] is an image under tau of the previous word w[i-1]. We define the complexity measure lambda A ,tau(n) , equal to the largest cardinality of a language X having words of length at most n , and st. some tau-Gray cycle over X exists. The present paper is concerned with tau = sigma k , the so-called k- character substitution, st. (u , v) E sigma k holds if, and only if, the Hamming distance of u and v is k. We present loopless (resp., constant amortized time) algorithms for computing specific maximum length sigma k-Gray cycles. (c) 2023 Elsevier B.V. All rights reserved.