Geography 4110/5100 Remote Sensing of the Environment Lecture: Tues.
10
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
Découvre YouScribe en t'inscrivant gratuitement
Découvre YouScribe en t'inscrivant gratuitement
10
pages
English
Documents
Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus
- cours magistral
- extent of vegetation cover
- ice sheet topography
- passive microwave radiometry
- relative resolution for various sensors
- types of orbits
- synthetic aperture radar
- spectral bands
- remote sensing
1
Order and quasiperiodicity in episturmian words
∗ Amy Glen LaCIM,Universit´eduQu´ebec`aMontre´al, C.P.8888,succursaleCentreville,Montre´al,Qu´ebec,CANADA,H3C3P8 † Extended Abstract
Introduction
July 13, 2007
In this paper, we build upon previous work concerning inequalities characterizing Sturmian and episturmian words – see [19, 29, 30, 14, 16]. First let us recall from [29] the following notion relating tolexicographic order. LetAbe atotally orderedfinite alphabet consisting of at least two letters. To any infinite wordxover A, we can associate two infinite words min(x) and max(x) such that any prefix of min(x) (resp. max(x)) is thelexicographicallysmallest (resp. greatest) amongst the factors ofxMore precisely, ifof the same length. we denote by min(x|k) (resp. max(x|k)) the lexicographically smallest (resp. greatest) factor ofxof length kfor the given order, then min(x|k) and max(x|k) are clearly prefixes of the respective words min(x|k+ 1) and max(x|kSo we can define, by taking limits, the following two infinite words+ 1).
min(xlim min() = x|k) k→∞
and
max(xlim max() = x|k). k→∞
An important point here is that, for any aperiodic infinite wordxwhich is uniformly recurrent, min(x) is aninfinite Lyndon word, i.e., it is (strictly) lexicographically smaller than all of its proper suffixes for the given order onA. In 2003, Pirillo [28] (also see [29]) proved that, for infinite wordsson a 2letter alphabet{a, b}with a < b, the inequalityas≤min(s)≤max(s)≤bscharacterizesstandard Sturmian words(aperiodic and periodic). Equivalently, an infinite sequences= (sn)n≥0over{a, b}is standard Sturmian if and only if
k as≤T (s)≤bs,
for allk≥0,
(1.1)
k k where T is thekth iterate of theshift map: T ((sn)n≥0) = (sn+k)n≥0(cf.our analogue for episturmian sequences – Corollary 3.2). Actually, this result was known much earlier, dating back to the work of P. Veerman [38, 39] in the mid 80’s. Since that time, these ‘Sturmian inequalities’ have been rediscovered numerous times under different guises, as discussed in our survey paper [4]. In the case of an arbitrary finite alphabetA, Pirillo [29] generalized the above inequalities by proving that an infinite wordsoverAisstandard episturmian(orepistandardfor short) if and only if, for any lexicographic order, we have as≤min(s) wherea= min(A).(1.2) Moreover,sis astrictepistandard word (i.e., astandard ArnouxRauzy sequence[7, 37]) if and only if (1.2) holds with strict equality for any order [19]. In a similar spirit, Glen, Justin, and Pirillo [16] recently proved the following characterization of allepisturmian words.
Proposition 1.1.[16]A recurrent infinite wordtoverAis episturmian if and only if there exists an infinite wordssuch that, for any lexicographic order, we haveas≤min(t)wherea= min(A).
From the proof of the above result, it is not immediately clear what form is taken by the infinite words, if it exists. We now prove further (in Section 3) thatsis in fact the ‘unique’ epistandard word with the same set of factors ast, i.e., the corresponding epistandard word in theshift orbit closureoft(see Section 2). As the title of this paper suggests, these results have a connection withquasiperiodicityexactly?. What Well, roughly speaking, an infinite wordxisquasiperiodicif there exists a finite wordusuch that the ∗ Email:amy.glen@gmail.com(with the support of CRMISMLaCIM) † Same as the full version, but all proofs (and some lemmas) have been omitted.
1
