復(fù)雜性與動(dòng)力系統(tǒng)

     目錄
   非線性科學(xué)叢書(shū)出版說(shuō)明
   前言
   第1章 形式語(yǔ)言與自動(dòng)機(jī)
    §1有限自動(dòng)機(jī)與正規(guī)語(yǔ)言
    §1.1有限自動(dòng)機(jī)的構(gòu)造
    §1.2關(guān)于形式語(yǔ)言的記號(hào)和概念
    §1.3有限自動(dòng)機(jī)的數(shù)學(xué)定義及其推廣
    §1.4狀態(tài)轉(zhuǎn)移圖
    §1.5正規(guī)表達(dá)式
    §1.6右線性語(yǔ)法
    §1.7正規(guī)語(yǔ)言的泵引理
    §1.8自然等價(jià)關(guān)系RL
    §1.9封閉性質(zhì)
    §2無(wú)限自動(dòng)機(jī)
    §2.1一般性討論
    §2.2下推自動(dòng)機(jī)
    §2.3有兩個(gè)堆棧的下推自動(dòng)機(jī)
    §2.4圖靈機(jī)
    §2.5遞歸語(yǔ)言與非遞歸可枚舉語(yǔ)言
    §2.6線性有界自動(dòng)機(jī)
    §3生成語(yǔ)法系統(tǒng)
    §3.1語(yǔ)言的喬姆斯基層次
    §3.2上下文無(wú)關(guān)語(yǔ)言的例子
    §3.3上下文無(wú)關(guān)語(yǔ)言的泵引理
    §3.4奧登引理
    §3.5關(guān)于兩個(gè)定理
    §3.6上下文有關(guān)語(yǔ)言
    §4并行重寫(xiě)系統(tǒng)
    §4.1最簡(jiǎn)單的L系統(tǒng)
    §4.2OL、TOL和ETOL系統(tǒng)
    §4.3語(yǔ)言類之間的關(guān)系
    §4.4關(guān)于ETOL的一些性質(zhì)
    §4.5標(biāo)號(hào)語(yǔ)言
   第2章 區(qū)間映射與形式語(yǔ)言
    §5區(qū)間映射的符號(hào)動(dòng)力學(xué)
    §5.1單峰映射
    §5.2符號(hào)動(dòng)力學(xué)
    §5.3符號(hào)序列之間的序
    §5.4必要條件和充分條件
    §6形式語(yǔ)言的定義
    §6.1從允許字定義形式語(yǔ)言
    §6.2揉序列含符號(hào)c的情況
    §6.3周期允許字與周期軌
    §6.4由語(yǔ)言確定揉序列
    §6.5語(yǔ)言定義的修改
    §6.6語(yǔ)言定義的另一種修改
   第3章 區(qū)間映射中的正規(guī)語(yǔ)言
    §7關(guān)于語(yǔ)言的一般性討論
    §7.1關(guān)于滿射情況的討論
    §7.2兩個(gè)簡(jiǎn)單例子
    §7.3關(guān)于正規(guī)語(yǔ)言的一般問(wèn)題
    §7.4兩個(gè)基本性質(zhì)
    §7.5判定法則
    §7.6符號(hào)串的前后綴
    §7.7判定法則的證明
    §8從揉序列判定正規(guī)性
    §8.1有限自動(dòng)機(jī)的特征分析
    §8.2計(jì)算RL等價(jià)類的例子
    §8.3主要結(jié)果及其證明
    §8.4逆定理及其意義
    §8.5文獻(xiàn)簡(jiǎn)述
    §8.6馬爾可夫劃分方法
    §8.7關(guān)于揉序列前綴的研究
    §9最小有限自動(dòng)機(jī)的構(gòu)造
    §9.1構(gòu)造自動(dòng)機(jī)的基本方法
    §9.2周期情況的最小自動(dòng)機(jī)
    §9.3例子
    §9.4終極周期情況的最小自動(dòng)機(jī)
    §9.5*合成律與廣義合成律
   第4章 區(qū)間映射中的非正規(guī)語(yǔ)言
    §10費(fèi)根鮑姆吸引子的形式語(yǔ)言
    §10.1倍周期分岔的極限
    §10.2重正化變換與揉序列
    §10.3t∞與TM序列
    §10.4語(yǔ)言Ψ（t∞）的結(jié)構(gòu)
    §11復(fù)雜性分析
    §11.1關(guān)于tn的一些性質(zhì)
    §11.2（t∞）不是CFL的證明
    §11.3（t∞）為ETOL語(yǔ)言的證明
    §11.4討論
    §12其他非正規(guī)語(yǔ)言
    §12.1關(guān)于 （t∞）的推廣
    §12.2斐波那契系統(tǒng)
    §12.3關(guān)于同態(tài)的幾個(gè)例子
    §12.4有待解決的問(wèn)題
   第5章 多樣性與禁止字
    §13形式語(yǔ)言的熵
    §13.1熵的定義
    §13.2關(guān)于熵的一些性質(zhì)
    §13.3計(jì)算熵的幾個(gè)例子
    §13.4伴隨矩陣方法
    §13.5生成函數(shù)與揉行列式
    §13.6與拓?fù)潇氐牡葍r(jià)性
    §14熵的計(jì)算和意義
    §14.1費(fèi)根鮑姆吸引子的熵
    §14.2關(guān)于熵的兩個(gè)計(jì)算公式
    §14.3熵與奇周期軌
    §14.4周期窗口的熵
    §14.5熵為零的動(dòng)力學(xué)意義
    §14.6熵與揉序列
    §15禁止字與正規(guī)語(yǔ)言
    §15.1關(guān)于禁止字的一般概念
    §15.2有限補(bǔ)語(yǔ)言
    §15.3禁止字的計(jì)算方法
    §15.4KS為周期序列時(shí)的禁止字
    §15.5KS為終極周期序列時(shí)的禁止字
    §16禁止字與非正規(guī)語(yǔ)言
    §16.1L和L″的喬姆斯基層次
    §16.2費(fèi)根鮑姆吸引子的禁止字
    §16.3偶斐波那契系統(tǒng)的禁止字
    §16.4奇斐波那契系統(tǒng)的禁止字
   第6章 元胞自動(dòng)機(jī)
    §17元胞自動(dòng)機(jī)的基本概念
    §17.1一維元胞自動(dòng)機(jī)
    §17.2幾種推廣
    §17.3元胞自動(dòng)機(jī)的一般特征
    §17.4動(dòng)力學(xué)行為的分類
    §17.5文獻(xiàn)簡(jiǎn)述
    §18一些數(shù)學(xué)記號(hào)與結(jié)果
    §18.1構(gòu)形空間與極限集
    §18.2冪零型元胞自動(dòng)機(jī)
    §18.3A（F）為無(wú)限集的情況
    §18.4周期點(diǎn)集合
    §18.5A（F）中點(diǎn)的逆向軌
    §19元胞自動(dòng)機(jī)中的正規(guī)語(yǔ)言
    §19.1F（Sz）的復(fù)雜性
    §19.2最小有限自動(dòng)機(jī)
    §19.376號(hào)元胞自動(dòng)機(jī)
    §19.4128號(hào)元胞自動(dòng)機(jī)
    §19.590號(hào)元胞自動(dòng)機(jī)
    §19.618號(hào)與22號(hào)元胞自動(dòng)機(jī)
    §20元胞自動(dòng)機(jī)中的非正規(guī)語(yǔ)言
    §20.1四類行為的出現(xiàn)頻率
    §20.2（A（F））為上下文無(wú)關(guān)語(yǔ)言的例子
    §20.3（A（F））為上下文有關(guān)語(yǔ)言的例子
    §20.4關(guān)于復(fù)雜性的一些理論結(jié)果
    §21空間熵與時(shí)間熵
    §21.1兩種不同的熵
    §21.2元胞自動(dòng)機(jī)的拓?fù)潇赜?jì)算
    §21.3舉例
    §21.4理論上的限制
   第7章 單個(gè)序列的復(fù)雜性
    §22柯?tīng)柲缏宸驈?fù)雜性
    §22.1單個(gè)符號(hào)序列的復(fù)雜性
    §22.2關(guān)于隨機(jī)性的討論
    §22.3描述復(fù)雜性
    §22.4柯?tīng)柲缏宸驈?fù)雜性的定義
    §23K（x）的性質(zhì)與應(yīng)用
    §23.1K（x）的基本性質(zhì)
    §23.2在自然數(shù)集上定義的K（x）
    §23.3K（x）在動(dòng)力系統(tǒng)中的應(yīng)用
    §23.4在形式語(yǔ)言中的一個(gè)應(yīng)用
    §24基于移位寄存器的復(fù)雜性
    §24.1移位寄存器序列
    §24.2幾個(gè)簡(jiǎn)單例子
    §24.3線性復(fù)雜性的計(jì)算方法
    §24.4特布里淵序列
    §24.5與K（x）的比較
    §25蘭帕爾－齊夫復(fù)雜性
    §25.1一種容易計(jì)算的復(fù)雜性
    §25.2理論基礎(chǔ)
    §25.3關(guān)于非等概率情況的修正
    §25.4在動(dòng)力系統(tǒng)中的應(yīng)用
   附錄A 本書(shū)§6中兩個(gè)定理的證明
    A.1定理1的證明
    A.2定理3的證明
   附錄B （KS）為正規(guī)語(yǔ)言的充分條件
    B.1關(guān)于周期揉序列的一個(gè)引理
    B.2定理2的證明
    B.3關(guān)于既約串的基本概念和事實(shí)
    B.4定理3的證明
    B.5循環(huán)移位最大字
   附錄C 關(guān)于§10.4的補(bǔ)充
    C.1命題的證明
    C.2推廣
    C.3從奇串平方開(kāi)始的移位最大字
    C.4其他例子
   附錄D 聯(lián)系N（t）與D（t）的公式
   參考文獻(xiàn)