Rich, Sturmian, and trapezoidal words
From MaRDI portal
Publication:955036
DOI10.1016/J.TCS.2008.06.009zbMATH Open1153.68045arXiv0802.3885OpenAlexW1979358057MaRDI QIDQ955036FDOQ955036
Authors: Amy Glen, Luca Q. Zamboni, Aldo De Luca 
Publication date: 18 November 2008
Published in: Theoretical Computer Science (Search for Journal in Brave)
Abstract: In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced in arXiv:0801.1656 by the second and third authors together with J. Justin and S. Widmer, constitute a new class of finite and infinite words characterized by having the maximal number of palindromic factors. Every finite Sturmian word is rich, but not conversely. Trapezoidal words were first introduced by the first author in studying the behavior of the subword complexity of finite Sturmian words. Unfortunately this property does not characterize finite Sturmian words. In this note we show that the only trapezoidal palindromes are Sturmian. More generally we show that Sturmian palindromes can be characterized either in terms of their subword complexity (the trapezoidal property) or in terms of their palindromic complexity. We also obtain a similar characterization of rich palindromes in terms of a relation between palindromic complexity and subword complexity.
Full work available at URL: https://arxiv.org/abs/0802.3885
Recommendations
Cites Work
- Title not available (Why is that?)
- Palindromic richness
- Episturmian words and some constructions of de Luca and Rauzy
- Palindromes and Sturmian words
- Palindromic complexity of infinite words associated with simple Parry numbers
- A connection between palindromic and factor complexity using return words
- Some characterizations of finite Sturmian words.
- COMBINATORIAL PROPERTIES OF STURMIAN PALINDROMES
- On the combinatorics of finite words
- Languages of k -interval exchange transformations
- Structure of \(K\)-interval exchange transformations: induction, trajectories, and distance theorems
- A combinatorial problem on trapezoidal words.
Cited In (21)
- A classification of trapezoidal words
- Complexity and palindromic defect of infinite words
- Extensions of rich words
- Palindromic rich words and run-length encodings
- Characteristic parameters and special trapezoidal words
- Special factors and the combinatorics of suffix and factor automata
- Closed, palindromic, rich, privileged, trapezoidal, and balanced words in automatic sequences
- A new characteristic property of rich words
- Ostrowski-automatic sequences: theory and applications
- On generalized highly potential words
- Rich and Periodic-Like Words
- Absent Subsequences in Words
- Enumeration and structure of trapezoidal words
- Scattered Factor-Universality of Words
- On the least number of palindromes contained in an infinite word
- Combinatorial algorithms for subsequence matching: a survey
- Generalized trapezoidal words
- Rich square-free words
- ALMOST RICH WORDS AS MORPHIC IMAGES OF RICH WORDS
- The repetition threshold for binary rich words
- Episturmian words: a survey
This page was built for publication: Rich, Sturmian, and trapezoidal words
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q955036)
