《複雜性與動力系統》是1994年上海科技教育出版社出版的圖書，作者是謝惠民。
基本介紹
- 作者：謝惠民
- ISBN：9787542808998
- 頁數：236
- 定價：15.80
- 出版社：上海科技教育出版社
- 出版時間：1994-08
- 裝幀：精裝
- 叢書： 非線性科學叢書
作品目錄,
作品目錄
目錄
非線性科學叢書出版說明
前言
第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）的公式
參考文獻
非線性科學叢書出版說明
前言
第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）的公式
參考文獻
