A classification of trapezoidal words
From MaRDI portal
Abstract: Trapezoidal words are finite words having at most n+1 distinct factors of length n, for every n>=0. They encompass finite Sturmian words. We distinguish trapezoidal words into two disjoint subsets: open and closed trapezoidal words. A trapezoidal word is closed if its longest repeated prefix has exactly two occurrences in the word, the second one being a suffix of the word. Otherwise it is open. We show that open trapezoidal words are all primitive and that closed trapezoidal words are all Sturmian. We then show that trapezoidal palindromes are closed (and therefore Sturmian). This allows us to characterize the special factors of Sturmian palindromes. We end with several open problems.
Recommendations
Cited in
(16)- A combinatorial problem on trapezoidal words.
- Enumeration and structure of trapezoidal words
- Trapezoid order classification
- On closed-rich words
- Off-line and on-line algorithms for closed string factorization
- Characteristic parameters and special trapezoidal words
- The sequence of open and closed prefixes of a Sturmian word
- Closed factorization
- Generalized trapezoidal words
- Efficient identification of k-closed strings
- Finite and infinite closed-rich words
- Asymptotic bounds for the number of closed and privileged words
- A symmetry property of Christoffel words
- Finding maximal closed substrings
- On palindromic periodicities
- Rich, Sturmian, and trapezoidal words
This page was built for publication: A classification of trapezoidal words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2789522)
