Download PDFOpen PDF in browserGray Cycles of Maximum Length Related to $K$Character SubstitutionsEasyChair Preprint 704712 pages•Date: November 14, 2021AbstractLet $A$ be a finite alphabet, $\tau\subseteq A^*\times A^*$ a word binary relation, and $X$ a finite subset of $A^*$. We define a $\tau${\it Gray cycle over} $X$ as every sequence $\left(w_{[i]}\right)_{0\le i\le X1}$ of paiwise different words satisfying each of the three following conditions: (i) for every $x\in X$, some $i\in [0,X1]$ exists such that $x=w_{[i]}$; (ii) for every $i\in [1,X1]$ the condition $w_{[i]}\in\tau\left(w_{[i1]}\right)$ holds; (iii) we have $w_{[0]}\in\tau\left(w_{[X1]}\right)$. In that framework, we introduce some complexity measure for $\tau$, namely $\lambda_{A,\tau}$, as indicated in the following: given a nonnegative integer $n$, the value $\lambda_{A,\tau}(n)$ stands for the maximum cardinality of the subsets $X$ of $A^{\le n}$ such that some $\tau$Gray cycle exists over $X$ (where $A^{\le n}$ denotes the set of the words no longer than $n$). We focus on the case where $\tau$ is the $k$character substitution, for some $k\ge 1$:by constructing convenient Gray cycles, we compute $\lambda_{A,\tau}(n)$. Keyphrases: Combinatorial Gray code, Gray code, ary reflected gray code, binary, binary alphabet, character, closed, combinatorial, complexity cycle, dependence, finite alphabet, gray, gray cycle, induction stage, k character substitution, k gray cycle, k satisfy condition, maximum length, relation, substitution, variablelength code, word, word binary relation
