# Generating a Gray code for prefix normal words in amortized polylogarithmic time per word

arXiv: https://arxiv.org/abs/2003.03222 · HTML: https://mlsanity.com/paper/2003.03222/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [Word Chain Generators for Prefix Normal Words](https://mlsanity.com/paper/2508.19619/) (2025)

## Abstract (arXiv)

A prefix normal word is a binary word with the property that no substring has more 1s than the prefix of the same length. By proving that the set of prefix normal words is a bubble language, we can exhaustively list all prefix normal words of length n as a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in Oh(log2 n) amortized time per word, while the best generation algorithm hitherto has Oh(n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.