Mathematics – Combinatorics
Scientific paper
2007-08-31
Theoretical Computer Science 391 (2008) 51-60
Mathematics
Combinatorics
16 pages; presented at the conference on "Combinatorics, Automata and Number Theory", Liege, Belgium, May 8-19, 2006 (to appea
Scientific paper
10.1016/j.tcs.2007.10.029
To any infinite word w over a finite alphabet A we can associate two infinite words min(w) and max(w) such that any prefix of min(w) (resp. max(w)) is the lexicographically smallest (resp. greatest) amongst the factors of w of the same length. We say that an infinite word w over A is "fine" if there exists an infinite word u such that, for any lexicographic order, min(w) = au where a = min(A). In this paper, we characterize fine words; specifically, we prove that an infinite word w is fine if and only if w 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.
No associations
LandOfFree
A characterization of fine words over a finite alphabet does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A characterization of fine words over a finite alphabet, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A characterization of fine words over a finite alphabet will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-618504