Journal article
A characterization of fine words over a finite alphabet
Theoretical Computer Science, Vol.391(1-2), pp.51-60
2008
Abstract
To any infinite word t over a finite alphabet A we can associate two infinite words min (t) and max (t) such that any prefix of min (t) (resp. max (t)) is the lexicographically smallest (resp. greatest) amongst the factors of t of the same length. We say that an infinite word t over A is fine if there exists an infinite word s such that, for any lexicographic order, min (t) = a s where a = min (A). In this paper, we characterize fine words; specifically, we prove that an infinite word t is fine if and only if t is either a strict episturmian word or a strict "skew episturmian word". This characterization generalizes a recent result of G. Pirillo, who proved that a fine word over a 2-letter alphabet is either an (aperiodic) Sturmian word, or an ultimately periodic (but not periodic) infinite word, all of whose factors are (finite) Sturmian.
Details
- Title
- A characterization of fine words over a finite alphabet
- Authors/Creators
- A. Glen (Author/Creator) - Université du Québec à Montréal
- Publication Details
- Theoretical Computer Science, Vol.391(1-2), pp.51-60
- Publisher
- Elsevier BV
- Identifiers
- 991005540135407891
- Copyright
- © 2007 Elsevier Ltd.
- Murdoch Affiliation
- Murdoch University
- Language
- English
- Resource Type
- Journal article
Metrics
214 File views/ downloads
76 Record Views
InCites Highlights
These are selected metrics from InCites Benchmarking & Analytics tool, related to this output
- 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