On collapsing prefix normal words

Abstract: Prefix normal words are binary words in which each prefix has at least the same number of

s o

s as any factor of the same length. Firstly introduced by Fici and Lipt'ak in 2011, the problem of determining the index of the prefix equivalence relation is still open. In this paper, we investigate two aspects of the problem, namely prefix normal palindromes and so-called collapsing words (extending the notion of critical words). We prove characterizations for both the palindromes and the collapsing words and show their connection. Based on this, we show that still open problems regarding prefix normal words can be split into certain subproblems.

Review text

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].

Recommendations

Cited in

(9)

This page was built for publication: On collapsing prefix normal words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q782603)