Gray Cycles of Maximum Length Related to $K$-Character Substitutions

EasyChair Preprint 7047

Abstract

Let $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 |X|-1}$ of paiwise different words satisfying each of the three following conditions: (i) for every $x\in X$, some $i\in [0,|X|-1]$ exists such that $x=w_{[i]}$; (ii) for every $i\in [1,|X|-1]$ the condition $w_{[i]}\in\tau\left(w_{[i-1]}\right)$ holds; (iii) we have $w_{[0]}\in\tau\left(w_{[|X|-1]}\right)$. In that framework, we introduce some complexity measure for $\tau$, namely $\lambda_{A,\tau}$, as indicated in the following: given a non-negative 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, variable-length code, word, word binary relation

@booklet{EasyChair:7047,
  author    = {Jean Néraud},
  title     = {Gray Cycles of Maximum Length Related to $K$-Character Substitutions},
  howpublished = {EasyChair Preprint 7047},
  year      = {EasyChair, 2021}}