More on Prefix Normal Words


Prefix normal words are binary words with the property that no substring has more 1s than the prefix of the same length. For example, the word 11010011 is prefix normal, while 11001101 is not: it has a substring of length 4 with 3 1s, while the prefix of length 4 has only 2 1s. It can be shown that every binary word has a canonical prefix normal form of the same length. These words were introduced in [Fici & Lipták, DLT 2011].

All prefix normal words of length n can be generated efficiently, based on the fact that they form a bubble language (a property introduced by Ruskey, Sawada, and Williams in 2012); moreover, they can be given as a Grey code. 

In this talk, I will present some of the insights we gained using this efficient generation algorithm. We are particularly interested in enumeration of subclasses of prefix normal words: counting all prefix normal words of a given length, counting fixed-density prefix normal words, counting extensions of prefix normal words.

Prefix normal words emerge in the context of Binary Jumbled Pattern Matching, a problem that has attracted much interest recently. In fact, prefix normal forms can be used for the indexed version of BJPM, so advances here could lead to improvements for the BJPM problem. 


This is joint work with Péter Burcsi, Gabriele Fici, Frank Ruskey, and Joe Sawada.