Generating a Gray code for prefix normal words in amortized polylogarithmic time per word
arXiv:2003.03222 · doi:10.1016/J.TCS.2020.07.035
Abstract
A prefix normal word is a binary word with the property that no substring has more s 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 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(\log^2 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.
To appear in Theoretical Computer Science. arXiv admin note: text overlap with arXiv:1401.6346