Generalized trapezoidal words

DOI10.1016/J.JCTA.2015.06.008MaRDI QIDQ490909zbMATH OpenOpenAlexFDO

Authors Amy Glen, Florence Levé

Publication date 21 August 2015

Published in Journal of Combinatorial Theory. Series A (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1408.0451

zbMATH Keywords

Sturmian wordpalindromeword complexitygeneralized trapezoidal wordrich wordtrapezoidal word

Mathematics Subject Classification ID

Combinatorics on words (68R15)

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

Recommendations

• Rich, Sturmian, and trapezoidal words
• A combinatorial problem on trapezoidal words.
• A classification of trapezoidal words
• Enumeration and structure of trapezoidal words
• Characteristic parameters and special trapezoidal words

Cites work

• scientific article; zbMATH DE number 1737190 (Why is no real title available?)
• A combinatorial problem on trapezoidal words.
• Enumeration and structure of trapezoidal words
• Episturmian words and some constructions of de Luca and Rauzy
• ON THE PALINDROMIC COMPLEXITY OF INFINITE WORDS
• On low-complexity bi-infinite words and their factors
• On the combinatorics of finite words
• Palindromes and Sturmian words
• Palindromic richness
• Rich, Sturmian, and trapezoidal words

Cited in

(5)

• A classification of trapezoidal words
• A combinatorial problem on trapezoidal words.
• Enumeration and structure of trapezoidal words
• Rich, Sturmian, and trapezoidal words
• Characteristic parameters and special trapezoidal words

This page was built for publication: Generalized trapezoidal words

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q490909)