DROPS

Document

DOI: 10.4230/LIPIcs.CPM.2025.22

Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time

Authors: Bowie Liu, Dennis Wong, Chan-Tong Lam, and Sio-Kei Im

Published in: LIPIcs, Volume 331, 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)

Abstract

We present a two-stage algorithm to generate a cyclic 2-Gray code for Lucas words. The first step involves a simple recursive algorithm that generates a cyclic 2-Gray code for Fibonacci words starting with a 0, which are strings that avoid p consecutive ones starting with a 0. Then, by considering the first and last blocks of 1s and concatenating lists of Fibonacci words starting with a 0 of different length n, we construct the first cyclic 2-Gray code for Lucas words. By using a dynamic programming approach, our algorithm generates each Lucas word and Fibonacci word in constant amortized time per string, using O(n³) space. The algorithm can also be modified to produce the first efficient algorithm for generating q-decreasing sequences in constant amortized time per string, also using O(n³) space. Our work extends a previous result on generating a cyclic 2-Gray code for q-decreasing sequences [Conference proceeding: International Conference and Workshop on Algorithms and Computation (WALCOM), LNCS 14549:91-102, 2024].

Cite as

Bowie Liu, Dennis Wong, Chan-Tong Lam, and Sio-Kei Im. Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time. In 36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 331, pp. 22:1-22:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.CPM.2025.22,
  author =	{Liu, Bowie and Wong, Dennis and Lam, Chan-Tong and Im, Sio-Kei},
  title =	{{Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time}},
  booktitle =	{36th Annual Symposium on Combinatorial Pattern Matching (CPM 2025)},
  pages =	{22:1--22:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-369-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{331},
  editor =	{Bonizzoni, Paola and M\"{a}kinen, Veli},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2025.22},
  URN =		{urn:nbn:de:0030-drops-231166},
  doi =		{10.4230/LIPIcs.CPM.2025.22},
  annote =	{Keywords: Lucas word, Fibonacci word, Fibonacci sequence, q-decreasing sequence, Gray code, CAT algorithm}
}

Search Results

Documents authored by Im, Sio-Kei

Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time

Abstract

Cite as

Thanks for your feedback!

Could not send message