無窮序列的幾類復(fù)雜度的研究.pdf

1、本文主要研究了無窮序列的三種復(fù)雜度,排列復(fù)雜度,阿貝爾復(fù)雜度,k-阿貝爾復(fù)雜度.排列復(fù)雜度以及阿貝爾復(fù)雜度的研究由來已久,k-阿貝爾復(fù)雜是一個詞上組合上比較新穎的研究領(lǐng)域.本文著重研究了兩類序列:Cantor-like序列,Rudin-Shapiro序列.
　　具體的說,首先利用Cantor-like序列右特殊因子的性質(zhì)計算了其排列復(fù)雜度,證明了其排列復(fù)雜度函數(shù)的差分序列的正則性,并給出了生成其排列復(fù)雜度函數(shù)差分序列的廣義自動機(jī),

2、進(jìn)而證明了Cantor-like序列的排列復(fù)雜度是正則的.其次研究了Rudin-Shapiro序列的部分和的性質(zhì),利用兩個字符集上無窮序列的阿貝爾復(fù)雜度與序列部分和的關(guān)系證明了Rudin-Shapiro序列的阿貝爾復(fù)雜度的正則性.另外研究了其阿貝爾復(fù)雜度函數(shù)的漸進(jìn)函數(shù)圖像函數(shù)的盒維數(shù).最后研究了Cantor序列的k-阿貝爾復(fù)雜度,并證明了其正則性.
　　Shallit,Rampersad,Charlier利用自動機(jī)序列的可判斷性理

3、論證明了如下結(jié)論：任意k-自動機(jī)序列的排列復(fù)雜度都是k-正則的.在第三章,利用Cantor-like序列因子的性質(zhì),給出了其排列復(fù)雜度函數(shù)的具體計算公式,證明了函數(shù)差分序列的正則性,進(jìn)而證明了函數(shù)本身的正則性.進(jìn)一步驗證了他們的結(jié)論.
　　Rampersad,Madill證明了paper-folding序列的阿貝爾復(fù)雜度函數(shù)是正則的,并在其文章的最后提出了如下開問題：任何一個k-自動機(jī)序列的阿貝爾復(fù)雜度是不是總是k-正則的.這個問

4、題無法利用Shallit等人的判定性理論解決.據(jù)所知,這個問題至今尚未解決.在第四章,首先研究Rudin-Shapiro序列的部分和,利用二字符集上無窮序列的阿貝爾復(fù)雜度與其部分和序列的關(guān)系,證明了Rudin-Shapiro序列的阿貝爾復(fù)雜度是正則的,對Rampersad,Madill提出的開問題給出了一個肯定性的例子.其次將其阿貝爾復(fù)雜度函數(shù)連續(xù)化得到一個新的函數(shù),并研究了新函數(shù)的連續(xù)性,可微性以及其函數(shù)圖像的盒維數(shù).
　　20

5、13年,Karhum¨aki,Saarela,Zamboni把阿貝爾復(fù)雜度的概念推廣到k-阿貝爾復(fù)雜度,計算了Sturmain序列的k-阿貝爾復(fù)雜度.Vandomme,Parreau,Rigo在2014年提出了如下猜想：Thue-Morse序列的2-阿貝爾復(fù)雜度是2-正則的.這一問題隨后被Greinecker,Rigo等人用不同的方法解決了.Greinecker在其文章中提出如下猜想：任何一個自動機(jī)序列的2-阿貝爾復(fù)雜度都是正則的.在第