Word Chain Generators for Prefix Normal Words
Not on the map. Why?
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.
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
5 of 16 references.
References · 5
- 2013Binary Jumbled Pattern Matching on Trees and Tree-Like Structurescited by 1
- 2014On Combinatorial Generation of Prefix Normal Wordscited by 1
- 2014Normal, Abby Normal, Prefix Normalcited by 1
- 2017Bubble-Flip -- A New Generation Algorithm for Prefix Normal Wordscited by 1
- 2020Generating a Gray code for prefix normal words in amortized polylogarithmic time per wordcited by 1
Built on by
Not cited yet.