復雜性與動力系統(tǒng)

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