目錄
非綫性科學叢書齣版說明
前言
第1章 形式語言與自動機
§1有限自動機與正規語言
§1.1有限自動機的構造
§1.2關於形式語言的記號和概念
§1.3有限自動機的數學定義及其推廣
§1.4狀態轉移圖
§1.5正規錶達式
§1.6右綫性語法
§1.7正規語言的泵引理
§1.8自然等價關係RL
§1.9封閉性質
§2無限自動機
§2.1一般性討論
§2.2下推自動機
§2.3有兩個堆棧的下推自動機
§2.4圖靈機
§2.5遞歸語言與非遞歸可枚舉語言
§2.6綫性有界自動機
§3生成語法係統
§3.1語言的喬姆斯基層次
§3.2上下文無關語言的例子
§3.3上下文無關語言的泵引理
§3.4奧登引理
§3.5關於兩個定理
§3.6上下文有關語言
§4並行重寫係統
§4.1最簡單的L係統
§4.2OL、TOL和ETOL係統
§4.3語言類之間的關係
§4.4關於ETOL的一些性質
§4.5標號語言
第2章 區間映射與形式語言
§5區間映射的符號動力學
§5.1單峰映射
§5.2符號動力學
§5.3符號序列之間的序
§5.4必要條件和充分條件
§6形式語言的定義
§6.1從允許字定義形式語言
§6.2揉序列含符號c的情況
§6.3周期允許字與周期軌
§6.4由語言確定揉序列
§6.5語言定義的修改
§6.6語言定義的另一種修改
第3章 區間映射中的正規語言
§7關於語言的一般性討論
§7.1關於滿射情況的討論
§7.2兩個簡單例子
§7.3關於正規語言的一般問題
§7.4兩個基本性質
§7.5判定法則
§7.6符號串的前後綴
§7.7判定法則的證明
§8從揉序列判定正規性
§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章 區間映射中的非正規語言
§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其他非正規語言
§12.1關於 （t∞）的推廣
§12.2斐波那契係統
§12.3關於同態的幾個例子
§12.4有待解決的問題
第5章 多樣性與禁止字
§13形式語言的熵
§13.1熵的定義
§13.2關於熵的一些性質
§13.3計算熵的幾個例子
§13.4伴隨矩陣方法
§13.5生成函數與揉行列式
§13.6與拓撲熵的等價性
§14熵的計算和意義
§14.1費根鮑姆吸引子的熵
§14.2關於熵的兩個計算公式
§14.3熵與奇周期軌
§14.4周期窗口的熵
§14.5熵為零的動力學意義
§14.6熵與揉序列
§15禁止字與正規語言
§15.1關於禁止字的一般概念
§15.2有限補語言
§15.3禁止字的計算方法
§15.4KS為周期序列時的禁止字
§15.5KS為終極周期序列時的禁止字
§16禁止字與非正規語言
§16.1L和L″的喬姆斯基層次
§16.2費根鮑姆吸引子的禁止字
§16.3偶斐波那契係統的禁止字
§16.4奇斐波那契係統的禁止字
第6章 元胞自動機
§17元胞自動機的基本概念
§17.1一維元胞自動機
§17.2幾種推廣
§17.3元胞自動機的一般特徵
§17.4動力學行為的分類
§17.5文獻簡述
§18一些數學記號與結果
§18.1構形空間與極限集
§18.2冪零型元胞自動機
§18.3A（F）為無限集的情況
§18.4周期點集閤
§18.5A（F）中點的逆嚮軌
§19元胞自動機中的正規語言
§19.1F（Sz）的復雜性
§19.2最小有限自動機
§19.376號元胞自動機
§19.4128號元胞自動機
§19.590號元胞自動機
§19.618號與22號元胞自動機
§20元胞自動機中的非正規語言
§20.1四類行為的齣現頻率
§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在自然數集上定義的K（x）
§23.3K（x）在動力係統中的應用
§23.4在形式語言中的一個應用
§24基於移位寄存器的復雜性
§24.1移位寄存器序列
§24.2幾個簡單例子
§24.3綫性復雜性的計算方法
§24.4特布裏淵序列
§24.5與K（x）的比較
§25蘭帕爾－齊夫復雜性
§25.1一種容易計算的復雜性
§25.2理論基礎
§25.3關於非等概率情況的修正
§25.4在動力係統中的應用
附錄A 本書§6中兩個定理的證明
A.1定理1的證明
A.2定理3的證明
附錄B （KS）為正規語言的充分條件
B.1關於周期揉序列的一個引理
B.2定理2的證明
B.3關於既約串的基本概念和事實
B.4定理3的證明
B.5循環移位最大字
附錄C 關於§10.4的補充
C.1命題的證明
C.2推廣
C.3從奇串平方開始的移位最大字
C.4其他例子
附錄D 聯係N（t）與D（t）的公式
參考文獻
· · · · · · (收起)