Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4655135 | Journal of Combinatorial Theory, Series A | 2015 | 30 Pages |
The factor complexity function Cw(n)Cw(n) of a finite or infinite word w counts the number of distinct factors of w of length n for each n≥0n≥0. A finite word w of length |w||w| is said to be trapezoidal if the graph of its factor complexity Cw(n)Cw(n) as a function of n (for 0≤n≤|w|0≤n≤|w|) is that of a regular trapezoid (or possibly an isosceles triangle); that is, Cw(n)Cw(n) increases by 1 with each n on some interval of length r , then Cw(n)Cw(n) is constant on some interval of length s , and finally Cw(n)Cw(n) decreases by 1 with each n on an interval of the same length r . Necessarily Cw(1)=2Cw(1)=2 (since there is one factor of length 0, namely the empty word), so any trapezoidal word is on a binary alphabet. Trapezoidal words were first introduced by de Luca (1999) when studying the behaviour of the factor complexity of finite Sturmian words , i.e., factors of infinite “cutting sequences”, obtained by coding the sequence of cuts in an integer lattice over the positive quadrant of R2R2 made by a line of irrational slope. Every finite Sturmian word is trapezoidal, but not conversely. However, both families of words (trapezoidal and Sturmian) are special classes of so-called rich words (also known as full words) – a wider family of finite and infinite words characterized by containing the maximal number of palindromes – studied in depth by the first author and others in 2009.In this paper, we introduce a natural generalization of trapezoidal words over an arbitrary finite alphabet AA, called generalized trapezoidal words (or GT-words for short). In particular, we study combinatorial and structural properties of this new class of words, and we show that, unlike the binary case, not all GT-words are rich in palindromes when |A|≥3|A|≥3, but we can describe all those that are rich.