Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order

Joe Sawada, Aaron Williams, Dennis Wong

Research output: Chapter in Book/Report/Conference proceedingConference contributionpeer-review

4 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, 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].

Original languageEnglish
Title of host publicationCombinatorics on Words - 13th International Conference, WORDS 2021, Proceedings
EditorsThierry Lecroq, Svetlana Puzynina
PublisherSpringer Science and Business Media Deutschland GmbH
Pages172-184
Number of pages13
ISBN (Print)9783030850876
DOIs
Publication statusPublished - 2021
Event13th International Conference on Combinatorics on Words, WORDS 2021 - Virtual, Online
Duration: 13 Sept 202117 Sept 2021

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume12847 LNCS
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference13th International Conference on Combinatorics on Words, WORDS 2021
CityVirtual, Online
Period13/09/2117/09/21

Fingerprint

Dive into the research topics of 'Inside the Binary Reflected Gray Code: Flip-Swap Languages in 2-Gray Code Order'. Together they form a unique fingerprint.

Cite this