On collapsing prefix normal words (Q782603)

Prefix normal words are binary words in which each prefix has at least the same number of 1s as any factor of the same length. The problem of determining the index, i.e., the amount of equivalence classes for a given word length of the prefix normal equivalence relation, is still open. The paper is focused on palindromes and extension-critical words. At first, it is proven that prefix normal palindromes play a special role since they are not pn-equivalent to any other word. The notion of extension-critical words is based on an iterative approach: compute the prefix normal words of length \(n + 1\) based on the prefix normal words of length \(n\). A prefix normal word \(w\) is called extension-critical if \(w1\) is not prefix normal. The set of extension-critical words is investigated by introducing an equivalence relation \textit{collapse}, grouping all extension-critical words that are pn-equivalent, leading to the fact that prefix normal palindromes and the collapsing relation (extension-critical words) are related. These results show that easy connections between prefix normal palindromes of different lengths cannot be expected. This leads to a characterization of collapsing words which can be extended to an algorithm determining the corresponding equivalence classes. For the entire collection see [Zbl 1435.68034].