On collapsing prefix normal words (Q782603)

From MaRDI portal
scientific article
Language Label Description Also known as
English
On collapsing prefix normal words
scientific article

    Statements

    On collapsing prefix normal words (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    27 July 2020
    0 references
    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].
    0 references
    binary words
    0 references
    prefix normal words
    0 references
    palindromes
    0 references
    extension-critical words
    0 references
    collapsing words
    0 references

    Identifiers