TY - GEN
T1 - Inside the Binary Reflected Gray Code
T2 - 13th International Conference on Combinatorics on Words, WORDS 2021
AU - Sawada, Joe
AU - Williams, Aaron
AU - Wong, Dennis
N1 - Publisher Copyright:
© 2021, Springer Nature Switzerland AG.
PY - 2021
Y1 - 2021
N2 - A flip-swap language is a set S of binary strings of length n such that S∪ { 0n} is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of k-ary Dyck words, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-Gray code when listed in binary reflected Gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flip-swap languages in O(n)-amortized per string, except for prefix normal words of length n which require O(n1.864) -amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett. 106(3):96−99, 2008].
AB - A flip-swap language is a set S of binary strings of length n such that S∪ { 0n} is closed under two operations (when applicable): (1) Flip the leftmost 1; and (2) Swap the leftmost 1 with the bit to its right. Flip-swap languages model many combinatorial objects including necklaces, Lyndon words, prefix normal words, left factors of k-ary Dyck words, and feasible solutions to 0-1 knapsack problems. We prove that any flip-swap language forms a cyclic 2-Gray code when listed in binary reflected Gray code (BRGC) order. Furthermore, a generic successor rule computes the next string when provided with a membership tester. The rule generates each string in the aforementioned flip-swap languages in O(n)-amortized per string, except for prefix normal words of length n which require O(n1.864) -amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett. 106(3):96−99, 2008].
UR - http://www.scopus.com/inward/record.url?scp=85115328005&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-85088-3_15
DO - 10.1007/978-3-030-85088-3_15
M3 - Conference contribution
AN - SCOPUS:85115328005
SN - 9783030850876
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 172
EP - 184
BT - Combinatorics on Words - 13th International Conference, WORDS 2021, Proceedings
A2 - Lecroq, Thierry
A2 - Puzynina, Svetlana
PB - Springer Science and Business Media Deutschland GmbH
Y2 - 13 September 2021 through 17 September 2021
ER -