# Gray Cycles of Maximum Length Related to k-Character Substitutions

arXiv: https://arxiv.org/abs/2108.13659 · HTML: https://mlsanity.com/paper/2108.13659/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 1 of its 25 references that are in the map.
- First posted on arXiv 31 Aug 2021.

## Builds on (most cited first, 1 of 1)

- [Variable-Length Codes Independent or Closed with respect to Edit Relations](https://mlsanity.com/paper/2104.14185/) (2021)

## Abstract (arXiv)

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.