Flip-swap languages in binary reflected Gray code order

Joe Sawada, Aaron Williams, Dennis Wong

Research output: Contribution to journalArticlepeer-review

3 Citations (Scopus)

Abstract

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, lattice paths with at most k flaws, 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 Vajnovszki (2008) [35].

Original languageEnglish
Pages (from-to)138-148
Number of pages11
JournalTheoretical Computer Science
Volume933
DOIs
Publication statusPublished - 14 Oct 2022

Keywords

  • BRGC
  • Binary reflected Gray code
  • Dyck words
  • Flip-swap language
  • Gray codes
  • Lyndon words
  • Necklaces

Fingerprint

Dive into the research topics of 'Flip-swap languages in binary reflected Gray code order'. Together they form a unique fingerprint.

Cite this