# Word Chain Generators for Prefix Normal Words

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 5 of its 16 references that are in the map.
- First posted on arXiv 27 Aug 2025.

## Builds on (most cited first, 5 of 5)

- [Binary Jumbled Pattern Matching on Trees and Tree-Like Structures](https://mlsanity.com/paper/1301.6127/) (2013)
- [On Combinatorial Generation of Prefix Normal Words](https://mlsanity.com/paper/1401.6346/) (2014)
- [Normal, Abby Normal, Prefix Normal](https://mlsanity.com/paper/1404.2824/) (2014)
- [Bubble-Flip -- A New Generation Algorithm for Prefix Normal Words](https://mlsanity.com/paper/1712.05876/) (2017)
- [Generating a Gray code for prefix normal words in amortized polylogarithmic time per word](https://mlsanity.com/paper/2003.03222/) (2020)

## Abstract (arXiv)

In 2011, Fici and Lipt'ak introduced prefix normal words. A binary word is prefix normal if it has no factor (substring) that contains more occurrences of the letter 1 than the prefix of the same length. Among the open problems regarding this topic are the enumeration of prefix normal words and efficient testing methods. We show a range of characteristics of prefix normal words. These include properties of factors that are responsible for a word not being prefix normal. With word chains and generators, we introduce new ways of relating words of the same length to each other.