第一部分 背景与动机 3
第1章 DNA的结构与处理 3
1.1DNA的结构 3
1.2DNA分子的操作 9
引言 DNA计算简介 11
1.3读出序列 25
1.4文献注记 29
2.1Adleman实验 30
第2章 分子计算初步 30
2.2我们能否解决可满足性问题及破译DES密码 36
2.3计算模式——一些再思考 49
2.4DNA计算：希望与挑战 54
第二部分 数学理论 61
第3章 形式语言理论介绍 61
3.1基本记号，文法，自动机，文法系统 61
3.2递归可枚举语言的刻画 79
3.3通用图灵机和O型文法 87
3.4文献注记 94
4.1粘贴运算 96
第4章 粘贴系统 96
4.2粘贴系统及其分类 100
4.3粘贴系统的生成能力 105
4.4正则语言和线性语言的表示 112
4.5递归可枚举语言的刻画 115
4.6正则粘贴系统 118
4.7文献注记 124
5.1Watson-Crick有穷自动机 125
第5章 Watson-Crick自动机 125
5.2WK簇之间的关系 128
5.3递归可枚举语言的刻画 135
5.4Watson-Crick有穷转换器 139
5.5Watson-Crick有穷自动机的其他变形 140
5.6带有Watson-Crick内存的Watson-Crick自动机 146
5.7关于Watson-Crick自动机的通用性理论 151
5.8文献注记 157
6.1DNA结构中的插入－删除 158
第6章 插入－删除系统 158
6.2递归可枚举语言的刻画 159
6.3单字符插入－删除系统 170
6.4只使用插入运算 175
6.5文献注记 183
第7章 剪接系统 184
7.1从DNA重组到剪接运算 184
7.2作为语言运算的非迭代剪接 187
7.3作为语言运算的迭代剪接 195
7.4扩充H系统；生成能力 206
7.5简单H系统 213
7.6文献注记 218
第8章 有穷H系统的通用性 220
8.1用2－剪接代替1－剪接 220
8.2允许和禁止上下文 221
8.3目标语言 231
8.4程序化系统和进化系统 236
8.5双剪接H系统 248
8.6多重集合 251
8.7通用性结果 258
8.8文献注记 262
第9章 剪接循环串 264
9.1循环串的剪接运算变量 264
9.2一个变形变量及其能力 267
9.3文献注记 275
第10章 分布式H系统 276
10.1剪接文法系统 276
10.2通信分布式H系统 284
10.3双层分布式H系统 294
10.4分时分布式H系统 300
10.5计算完备性H系统的总结 305
10.6文献注记 306
第11章 再述剪接 308
11.1受限剪接：非重复情况 308
11.2复制系统 315
11.3文献注记 328
参考文献 329