Generalized trapezoidal words (Q490909)

From MaRDI portal
Revision as of 19:17, 9 December 2024 by Import241208061232 (talk | contribs) (Normalize DOI.)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
Generalized trapezoidal words
scientific article

    Statements

    Generalized trapezoidal words (English)
    0 references
    0 references
    0 references
    21 August 2015
    0 references
    The factor complexity \(C_w(n)\) of a word \(w\) of length \(\ell\) is the function that, for each \(n\in\{0,1,\dots,\ell\}\), returns the number of distinct factors of \(w\) of length \(n\). The word \(w\) is called trapezoidal if \(C_w(n)\) increases by 1 for each \(n\) in the interval \([0,r]\) for some \(r\leq\ell/2\), is constant for each \(n\) in the interval \([r,\ell-r]\), and decreases by 1 for each \(n\) in the interval \([\ell-r,\ell]\). Any trapezoidal word is necessarily over a binary alphabet. The authors suggest the following generalization. A word \(w\) of length \(\ell\) is called a generalized trapezoidal word (GT-word) if there exist positive integers \(m, M\) with \(m\leq M\leq\ell\) such that \(C_w(n)\) increases by 1 for each \(n\) in the interval \([1,m]\), is constant for each \(n\) in the interval \([m,M]\), and decreases by 1 for each \(n\) in the interval \([M,\ell]\). GT-words exist over any alphabet and the binary GT-words are precisely the trapezoidal words. The first main result of the paper (Theorem 17) nicely characterizes GT-words in terms of their hearts where the heart of a word \(w\) that contains at least two occurrences of some letter is the unique factor of \(w\) that remains if one erases the longest prefix and the longest suffix of \(w\) that contain letters only occurring once in \(w\). A word of length \(\ell\) is rich if it has \(\ell+1\) distinct palindromic factors. The second main result (Theorem 27) gives a complete characterization of the rich GT-words in terms of the hearts and the longest palindromic prefixes and suffixes of the hearts; its proof in the paper is very technical.
    0 references
    word complexity
    0 references
    trapezoidal word
    0 references
    generalized trapezoidal word
    0 references
    Sturmian word
    0 references
    palindrome
    0 references
    rich word
    0 references

    Identifiers