Word Chain Generators for Prefix Normal Words
This work addresses a theoretical problem in combinatorics for researchers studying prefix normal words, but it appears incremental as it builds on existing concepts without claiming major breakthroughs.
The paper tackled the problem of enumerating and testing prefix normal words by introducing word chains and generators to relate words of the same length, but no concrete results or numbers were provided.
In 2011, Fici and Lipták 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.