Generating Cyclic 2-Gray Codes for Fibonacci q-Decreasing Words

Dennis Wong, Bowie Liu, Chan Tong Lam, Marcus Im

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

Abstract

We present a two-stage algorithm for generating cyclic 2-Gray codes for q-decreasing words. In the first step, a simple recursive algorithm is used to generate a cyclic 2-Gray code for q-run constrained words, which are q-decreasing words that start with a 0. Then, by considering the first block of 1 s and concatenating cyclic Gray code listings of q-run constrained words of different length n, we construct the first known cyclic 2-Gray code for q-decreasing words for all positive real numbers q.

Original languageEnglish
Title of host publicationWALCOM
Subtitle of host publicationAlgorithms and Computation - 18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024, Proceedings
EditorsRyuhei Uehara, Katsuhisa Yamanaka, Hsu-Chun Yen
PublisherSpringer Science and Business Media Deutschland GmbH
Pages91-102
Number of pages12
ISBN (Print)9789819705658
DOIs
Publication statusPublished - 2024
Event18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024 - Kanazawa, Japan
Duration: 18 Mar 202420 Mar 2024

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume14549 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference18th International Conference and Workshops on Algorithms and Computation, WALCOM 2024
Country/TerritoryJapan
CityKanazawa
Period18/03/2420/03/24

Keywords

  • Fibonacci cube
  • Fibonacci sequence
  • Fibonacci word
  • Gray code
  • hypercube
  • q-decreasing word
  • Qubonacci word
  • run-constrained word

Fingerprint

Dive into the research topics of 'Generating Cyclic 2-Gray Codes for Fibonacci q-Decreasing Words'. Together they form a unique fingerprint.

Cite this