本文選題：自動機序列　切入點：正則序列　出處：《華中科技大學》2016年博士論文

【摘要】：本文主要研究了一類整數(shù)序列的正則性,并將有限字符集上的代換和有限自動機的概念推廣到了無窮字符集上.同時研究了無窮字符集上的代換和無窮狀態(tài)自動機所生成序列的正則性.最后研究了一類由Cantor-like序列生成sum-free集的一些性質,著重研究了它們的正則性.具體的說,我們研究了三類序列的正則性問題：第一類是序列.(「log6(an-β)」}n≥0的正則性刻畫.我們利用語言的正則性,證明了序列{「log6(an-β)」}n≥0是正則的當且僅當α∈Q.第二類是由無窮字符集上的代換和無窮狀態(tài)自動機所生成的序列.將其與有限字符集上的代換和有限自動機的性質進行比較,重點研究它們生成序列的正則性問題,以及在線性回歸投影下正則性不變的等價刻畫.己知取值有限的正則序列就是自動機序列這一結論,我們也給出了一種判斷序列非自動機的準則.第三類則是由Cantor-like序列和一些特殊的代換序列所生成的sum-free集.這樣的sum-free集可以被看作是整數(shù)序列.我們研究它們的正則性,并討論了一類sum-free集所對應的0—1序列的自動機性質.令α,β∈R,b≥2是一個整數(shù).Allouche和Shallit證明了序列[「an+β」}n≥0是6-正則的當且僅當a是有理數(shù).在第三章,我們主要討論了語言的正則性問題.利用給出的一類特殊的語言的正則性與基的變換無關的性質,證明了序列{11ogb(an+β)」}≥0的正則性的等價刻畫,即它是正則的當且僅當α∈Q,這個結論不僅回答了Allouche和Shallit提出的問題,更是對這個問題的進一步擴展.在第四章,我們首先給出了關于無窮字符集上的代換和無窮狀態(tài)自動機的定義和一些基本性質.然后重點研究了由它們生成的序列的正則性問題,并給出了產生一些非正則序列的條件.接下來給出了一類在線性回歸投影下序列正則性的等價刻畫.又根據正則序列和自動機序列之間的關系,間接給出了一個判斷序列非自動機的準則.在本章的最后,給出了關于無窮狀態(tài)自動機的一些基本拓展,并研究了由它生成序列的部分性質.Cameron介紹了在sum-free集合所有0—1序列構成的集合之間的一個雙射.在第五章,我們首先給出了關于sum-free集的研究背景和研究現(xiàn)狀.我們給出了一類由Cantor-like序列和一些特殊的代換序列所生成的自然數(shù)上的sum-free集,并且證明了這樣生成的sum-free集是2-正則的.同時反過來考慮了一類特殊的sum-free集所對應的0—1序列的自動機性質.在最后一章,我們首先系統(tǒng)的總結了一下本文的主要結果,然后針對每個結果給出了說明以及進一步研究的方向.
[Abstract]:In this paper, we study the regularity of a class of integer sequences. The concepts of substitution and finite automaton on finite character set are extended to infinite character set. At the same time, the regularity of sequences generated by substitution and infinite state automata on infinite character set is studied. Some properties of generating sum-free sets from Cantor-like sequences, In this paper, we focus on their regularity. Specifically, we study the regularity of three classes of sequences: the first is the regularity characterization of sequence. ("log6an- 尾)"} n 鈮，

本文編號：1656140