Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order
From MaRDI portal
Publication:6367136
DOI10.1007/978-3-030-85088-3_15arXiv2105.03556MaRDI QIDQ6367136FDOQ6367136
Dennis Wong, Aaron Williams, Joe Sawada
Publication date: 7 May 2021
Abstract: A flip-swap language is a set S of binary strings of length n such that 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()-amortized per string. Our work generalizes results on necklaces and Lyndon words by Vajnovski [Inf. Process. Lett. 106(3):9699, 2008].
This page was built for publication: Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6367136)
