@inproceedings{73c52f1274e64875859233d161a7e113,
title = "Generating a Cyclic 2-Gray Code for Lucas Words in Constant Amortized Time",
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(n3) 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(n3) 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].",
keywords = "CAT algorithm, Fibonacci sequence, Fibonacci word, Gray code, Lucas word, q-decreasing sequence",
author = "Bowie Liu and Dennis Wong and Lam, \{Chan Tong\} and Im, \{Sio Kei\}",
note = "Publisher Copyright: {\textcopyright} Bowie Liu, Dennis Wong, Chan-Tong Lam, and Sio-Kei Im;; 36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025 ; Conference date: 17-06-2025 Through 19-06-2025",
year = "2025",
month = jun,
day = "10",
doi = "10.4230/LIPIcs.CPM.2025.22",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing",
editor = "Paola Bonizzoni and Veli Makinen",
booktitle = "36th Annual Symposium on Combinatorial Pattern Matching, CPM 2025",
address = "Germany",
}