Generalized trapezoidal words (Q490909): Difference between revisions

From MaRDI portal
Set OpenAlex properties.
Normalize DOI.
 
(3 intermediate revisions by 3 users not shown)
Property / DOI
 
Property / DOI: 10.1016/j.jcta.2015.06.008 / rank
Normal rank
 
Property / arXiv ID
 
Property / arXiv ID: 1408.0451 / rank
 
Normal rank
Property / cites work
 
Property / cites work: ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS / rank
 
Normal rank
Property / cites work
 
Property / cites work: Enumeration and structure of trapezoidal words / rank
 
Normal rank
Property / cites work
 
Property / cites work: A combinatorial problem on trapezoidal words. / rank
 
Normal rank
Property / cites work
 
Property / cites work: On the combinatorics of finite words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Rich, Sturmian, and trapezoidal words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Episturmian words and some constructions of de Luca and Rauzy / rank
 
Normal rank
Property / cites work
 
Property / cites work: Palindromes and Sturmian words / rank
 
Normal rank
Property / cites work
 
Property / cites work: Palindromic richness / rank
 
Normal rank
Property / cites work
 
Property / cites work: On low-complexity bi-infinite words and their factors / rank
 
Normal rank
Property / cites work
 
Property / cites work: Q4529547 / rank
 
Normal rank
Property / DOI
 
Property / DOI: 10.1016/J.JCTA.2015.06.008 / rank
 
Normal rank

Latest revision as of 19:17, 9 December 2024

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