Logo image
Back
Generalized trapezoidal words
Journal article   Open access   Peer reviewed

Generalized trapezoidal words

A. Glen and F. Levé
Journal of Combinatorial Theory, Series A, Vol.136, pp.96-125
2015
DOI: https://doi.org/10.1016/j.jcta.2015.06.008
pdf
generalized_trapezoidal_words.pdfDownloadView
Author’s VersionCC BY-NC-ND V4.0,  Open Access
url
Link to Published Version *Subscription may be requiredView

Abstract

The factor complexity function Cw(n) of a finite or infinite word w counts the number of distinct factors of w of length n for each n≥. 0. A finite word w of length |w| is said to be trapezoidal if the graph of its factor complexity Cw(n) as a function of n (for 0≤n≤|w|) is that of a regular trapezoid (or possibly an isosceles triangle); that is, Cw(n) increases by 1 with each n on some interval of length r, then Cw(n) is constant on some interval of length s, and finally Cw(n) decreases by 1 with each n on an interval of the same length r. Necessarily Cw(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 R2 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 A, 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, but we can describe all those that are rich.

Details

Metrics

95 File views/ downloads
84 Record Views

InCites Highlights

These are selected metrics from InCites Benchmarking & Analytics tool, related to this output

Collaboration types
Domestic collaboration
International collaboration
Citation topics
9 Mathematics
9.28 Pure Maths
9.28.534 Dynamical Systems
Web Of Science research areas
Mathematics
ESI research areas
Mathematics
Logo image