《复杂性与动力系统》求取 ⇩

第1章形式语言与自动机1

1 有限自动机与正规语言1

1.1 有限自动机的构造1

1.2 关于形式语言的记号和概念3

1.3 有限自动机的数学定义及其推广4

1.4 状态转移图6

1.5 正规表达式7

1.6 右线性语法9

1.7 正规语言的泵引理9

1.8 自然等价关系 RL10

1.9 封闭性质12

2 无限自动机13

2.1 一般性讨论13

2.2 下推自动机14

2.3 有两个堆栈的下推自动机15

2.4 图灵机16

2.5 递归语言与非递归可枚举语言18

2.6 线性有界自动机19

3 生成语法系统20

3.1 语言的乔姆斯基层次20

3.2 上下文无关语言的例子22

3.4 奥登引理24

3.5 关于?2和?3的两个定理25

3.6 上下文有关语言26

4 并行重写系统29

4.1 最简单的 L 系统29

4.2 OL、TOL 和 ETOL 系统30

4.3 语言类之间的关系33

3.3 上下文无关语言的泵引理33

4.4 关于 ETOL 的一些性质34

4.5 标号语言35

第2章区间映射与形式语言38

5 区间映射的符号动力学38

5.1 单峰映射38

5.2 符号动力学40

6.3 符号序列之间的序42

6.4 必要条件和充分条件43

6 形式语言的定义45

6.1 从允许字定义形式语言45

6.2 揉序列含符号 c 的情况47

6.3 周期允许字与周期轨48

6.4 由语言确定揉序列50

6.5 语言定义的修改50

6.6 语言定义的另一种修改51

第3章区间映射中的正规语言53

7 关于语言的一般性讨论54

7.1 关于满射情况的讨论54

7.2 两个简单例子56

7.3 关于正规语言的一般问题58

7.4 ?(KS)的两个基本性质58

7.6 z∈?(KS)的判定法则59

7.6 符号串的前后缀60

7.7 判定法则的证明61

8 从揉序列判定正规性62

8.1 有限自动机的特征分析63

8.2 计算 RL 等价类的例子65

8.3 主要结果及其证明66

8.4 逆定理及其意义69

8.5 文献简述71

8.6 马尔可夫划分方法72

8.7 关于揉序列前缀的研究74

9 最小有限自动机的构造76

9.1 构造自动机的基本方法76

9.2 周期情况的最小自动机78

9.4 终极周期情况的最小自动机81

9.3 例子81

9.5 *合成律与广义合成律84

第4章区间映射中的非正规语言87

10 费根鲍姆吸引子的形式语言87

10.1 倍周期分岔的极限87

10.2 重正化变换与揉序列89

10.3 t∞与 TM 序列92

10.4 语言?(t∞)的结构94

11 复杂性分析96

11.1 关于 tn 的一些性质96

11.2 ?(t∞)不是 OFL 的证明97

11.3 ?(t∞)为 ETOL 语言的证明99

11.4 讨论102

12 其他非正规语言103

12.1 关于?(t∞)的推广103

12.2 斐波那契系统105

12.3 关于同态的几个例子107

12.4 有待解决的问题109

第5章多样性与禁止字112

13 形式语言的熵112

13.1 熵的定义112

13.2 关于熵的一些性质115

13.3 计算熵的几个例子116

13.4 伴随矩阵方法119

13.5 生成函数与揉行列式120

13.6 与拓扑熵的等价性122

14 熵的计算和意义125

14.1 费根鲍姆吸引子的熵125

14.2 关于熵的两个计算公式126

14.3 熵与奇周期轨127

14.4 周期窗口的熵130

14.5 熵为零的动力学意义132

15 禁止字与正规语言133

15.1 关于禁止字的一般概念133

14.6 熵与揉序列133

15.2 有限补语言136

15.3 禁止字的计算方法138

15.4 KS 为周期序列时的禁止字139

15.5 KS 为终极周期序列时的禁止字139

16 禁止字与非正规语言141

16.1 L 和 L〃的乔姆斯基层次141

16.2 费根鲍姆吸引子的禁止字144

16.3 偶斐波那契系统的禁止字147

16.4 奇斐波那契系统的禁止字148

17.1 一维元胞自动机151

17 元胞自动机的基本概念151

第6章元胞自动机151

17.2 几种推广153

17.3 元胞自动机的一般特征155

17.4 动力学行为的分类156

17.6 文献简述157

18 一些数学记号与结果158

18.1 构形空间与极限集158

18.2 幂零型元胞自动机160

18.3 Λ(F)为无限集的情况161

18.4 周期点集合162

18.5 Λ(F)中点的逆向轨163

19 元胞自动机中的正规语言165

19.1 F(Sz)的复杂性165

19.2 最小有限自动机167

19.3 76号元胞自动机169

19.4 128号元胞自动机170

19.5 90号元胞自动机171

19.6 18号与22号元胞自动机172

20 元胞自动机中的非正规语言173

20.1 四类行为的出现频率174

20.2 ?(Λ(F))为上下文无关语言的例子175

20.3 ?(Λ(F))为上下文有关语言的例子177

20.4 关于复杂性的一些理论结果178

21 空间熵与时间熵180

21.1 两种不同的熵180

21.2 元胞自动机的拓扑熵计算181

21.3 举例182

21.4 理论上的限制184

第7章单个序列的复杂性186

22 柯尔莫哥洛夫复杂性186

22.1 单个符号序列的复杂性186

22.2 关于随机性的讨论188

22.3 描述复杂性189

22.4 柯尔莫哥洛夫复杂性的定义190

23 K(x)的性质与应用191

23.1 K(x)的基本性质191

23.2 在自然数集上定义的 K(x)193

23.3 K(x)在动力系统中的应用194

23.4 在形式语言中的一个应用196

24 基于移位寄存器的复杂性197

24.1 移位寄存器序列197

24.2 几个简单例子199

24.3 线性复杂性的计算方法200

24.4 特布里渊序列201

24.5 与 K(x)的比较203

26 兰帕尔-齐夫复杂性204

25.1 一种容易计算的复杂性204

25.2 理论基础207

25.3 关于非等概率情况的修正208

25.4 在动力系统中的应用209

附录A本书6中两个定理的证明212

A.1 定理1的证明212

A.2 定理3的证明215

B.1 关于周期揉序列的一个引理217

附录B?(KS)为正规语言的充分条件217

B.2 定理2的证明218

B.3 关于既约串的基本概念和事实218

B.4 定理3的证明219

B.5 循环移位最大字221

附录C关于10.4的补充222

C.1 命题的证明222

C.2 推广223

C.3 从奇串平方开始的移位最大字223

C.4 其他例子224

附录D 联系 N(t)与 D(t)的公式225

参考文献229