Logo image
Back
Rich, Sturmian, and trapezoidal words
Journal article   Open access   Peer reviewed

Rich, Sturmian, and trapezoidal words

A. De Luca, A. Glen and L. Zamboni
Theoretical Computer Science, Vol.407(1-3), pp.569-573
2008
DOI: https://doi.org/10.1016/j.tcs.2008.06.009
pdf
sturmian.pdfDownloadView
Author’s Version Open Access
url
Free to Read *No subscription requiredView

Abstract

In this paper we explore various interconnections between rich words, Sturmian words, and trapezoidal words. Rich words, first introduced 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.

Details

Metrics

237 File views/ downloads
94 Record Views
26 Times Cited - Web of Science

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
Computer Science, Theory & Methods
ESI research areas
Computer Science
Logo image