Accéder directement au contenu Accéder directement à la navigation
Pré-publication, Document de travail

Gray codes for Fibonacci q-decreasing words

Abstract : An $n$-length binary word is $q$-decreasing, $q\geq 1$, if every of its length maximal factor of the form $0^a1^b$ satisfies $a=0$ or $q\cdot a > b$.We show constructively that these words are in bijection with binary words having no occurrences of $1^{q+1}$, and thus they are enumerated by the $(q+1)$-generalized Fibonacci numbers. We give some enumerative results and reveal similarities between $q$-decreasing words and binary words having no occurrences of $1^{q+1}$ in terms of frequency of $1$ bit. In the second part of our paper, we provide an efficient exhaustive generating algorithm for $q$-decreasing words in lexicographic order, for any $q\geq 1$, show the existence of 3-Gray codes and explain how a generating algorithm for these Gray codes can be obtained. Moreover, we give the construction of a more restrictive 1-Gray code for $1$-decreasing words, which in particular settles a conjecture stated recently in the context of interconnection networks by E\u{g}ecio\u{g}lu and Ir\v{s}i\v{c}.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

https://hal-univ-bourgogne.archives-ouvertes.fr/hal-03114503
Contributeur : Sergey Kirgizov <>
Soumis le : mardi 19 janvier 2021 - 00:01:48
Dernière modification le : mardi 19 janvier 2021 - 03:28:52

Lien texte intégral

Identifiants

  • HAL Id : hal-03114503, version 1
  • ARXIV : 2010.09505

Citation

Jean-Luc Baril, Sergey Kirgizov, Vincent Vajnovszki. Gray codes for Fibonacci q-decreasing words. 2020. ⟨hal-03114503⟩

Partager

Métriques

Consultations de la notice

11