posted on 2020-06-26, 14:54authored byPeter Burcsi, Gabriele Fici, Zsuzsanna Liptak, Rajeev Raman, Joe Sawada
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 nas a combinatorial Gray code, where successive strings differ by at most two swaps or bit flips. This Gray code can be generated in O (log2n) amortized time per word, while the best generation algorithm hither to has O (n) running time per word. We also present a membership tester for prefix normal words, as well as a novel characterization of bubble languages.
History
Citation
Theoretical Computer Science
Volume 842, 24 November 2020, Pages 86-99