特徵字因子的位置

令α 是界在0 到1 的無理數。fα 表示為特徵字, 也就是, 若[(n + 1)α] − [nα] = 0, 則第n 個字母是a, 如果[(n + 1)α] − [nα] = 1, 則第n 個字母是b 的無窮字。特徵字因子w 的位置集就是w 出現在特徵字fα 所有位置的集合。我們利用特徵字的某些分解和非負整數的Zeckendorf 表現找到特徵字fα 所有因子的位置。此結果推廣了當特徵字的α = 3¡p5 2 或α = p5¡1 2 時, 由 Chuan 和Ho (2005) 所得到的結果。我們藉由給定特徵字fα 因子的長度及它出現在特徵字的位置, 求出此因子第一次出現在特徵字fα的次序來認出此因子。令w(t) 是w 第t 次出現在特徵字fα 的字。w 的第t 個return word 是開始在w(t) 出現在特徵字fα 的位置且結束在w(t+1) 出現的前一個位置。令Rt(w), 簡寫成Rt, 是w 的第t 個 return word。令集合Rα(w) = {Rt : t ≥ 1}。令yt 是使得Rt = w(t)yt 的字。Vuillon (2001) 證出Rα(w) 是個只有兩個元素的集合, 因此Bα(w) 也是。特徵字fα 可用w 的return word 來表示, 即fα = sR1R2R3 · · · , 其中s 是特徵字fα 的字首。因此, 特徵字也可用w(t) 和yt 表示, 即fα = sw(1)y1w(2)y2w(3)y3 · · · 。對某個無理數γ, 定義fγ(u, v) 是由fγ 中的字母a 用u 替代, fγ 中的字母b 用u 替代所得到的無窮字。對於某個無理數βα(w) 及u, v 是屬於集合Rα(w) 的兩個字, 如果R1R2R3 · · · = fβα(w)(u, v), 則此分解fα = sR1R2R3 · · · 表示為REDα(w)。對於某個無理數βα(w) 及u, v 是屬於集合Bα(w) 的兩個字, 如果y1y2y3 · · · = fβα(w)(u, v), 則此分解fα = sw(1)y1w(2)y2w(3)y3 · · · 表示為SODα(w)。我們證明特徵字fα 的每個因子w 都可以決定REDα(w) 與SODα(w) 這兩種分解。REDα(w) 是個包括w 的所有return words 的分解, SODα(w) 是個包括w 的所有overlap factors 和separate factors 的分解。我們推廣了由以下這些作者所得到的結果: Z.-X. Wen 和Z.-Y. Wen (1994), G. Melan¸con (1999), W.-T. Cao 和Z.-Y. Wen (2003), I.M. Ara´ujo 和V. Bruy`ere (2005), A. Glen (2006)。

關鍵字

分解；位置集；特徵字

並列摘要

Let α be an irrational number with 0 < α < 1. Denote by fα the characteristic word, that is, fα is the infinite word whose nth letter is a (resp., b) if [(n+1)α]−[nα] = 0 (resp., 1), n ≥ 1. For a factor w of fα, the location of w is the set of all positions in fα at which w occurs. We determine the locations of all factors of fα. One is using a decomposition of fα with respect to the occurrences of a factor of fα and the other one is using the Zeckendorf representation of nonnegative integers. We extend the results obtained by Chuan and Ho (2005) when α = 3¡p5 2 ( p5¡1 2 as well). Given the length of a factor and the position at which it occurs in fα, we are able to identify this factor by computing its order of their first occurrence in fα. Let w(t) denote the tth occurrence of w in fα. The tth return word of w in fα is a word that starts at an occurrence of w(t) in fα and ends exactly before the occurrence of w(t+1). Let Rt(w), or simply Rt be the tth return word of w. Denote by Rα(w) = {Rt : t ≥ 1}. Let yt be the words such that Rt = w(t)yt. Denote by Bα(w) = {yt : t ≥ 1}. Vuillon (2001) proved that Rα(w), and hence Bα(w), is always a 2-element set. In terms of the return words of w, we have fα = sR1R2R3 · · · , where s is a prefix of fα and thus, in terms of w(t) and yt, we have fα = sw(1)y1w(2)y2w(3)y3 · · · . Define fγ(u, v), for some irrational number γ, the infinite word obtained from fγ by substituting u for a and v for b. If R1R2R3 · · · = fβα(w)(u, v), for some irrational number βα(w) and u, v belong to the set Rα(w), then the decomposition fα = sR1R2R3 · · · is denoted by REDα(w). If y1y2y3 · · · = fβα(w)(u, v), where u, v belong to the set Bα(w), then the decomposition fα = sw(1)y1w(2)y2w(3)y3 · · · is denoted by SODα(w). We show that each factor w of fα determines two decompositions REDα(w) and SODα(w). The first one contains all return words, and the second one involves overlap factors and separate factors of w. These results generalize the results obtained by Z.-X. Wen and Z.-Y. Wen (1994), G. Melan¸con (1999), W.-T. Cao and Z.-Y. Wen (2003), I.M. Ara´ujo and V. Bruy`ere (2005), A. Glen (2006).

並列關鍵字

Decomposition ； Location ； Characteristic word

參考文獻

[1] I.M. Ara´ujo, V. Bruy`ere, Words derivated from Sturmian words, Theoret. Comput.

[2] M. Bunder, K. Tognetti, The Zeckendorf representation and the golden sequence,

[3] W.-T. Cao, Z.-Y. Wen, Some properties of the factors of Sturmian sequences, Theoret.

[4] W.-F. Chuan, Embedding Fibonacci words into Fibonacci word patterns, in: G.E.

Bergum, A.N. Philippou, A.F. Horadam (Eds.), Applications of Fibonacci Numbers,

國際替代計量

特徵字因子的位置

全文下載

主題瀏覽