良结构下推系统的表达能力

摘要

良结构下推系统是将状态集和栈字符集都扩展为良拟序集的下推系统，它是一个一般化的模型，一个自然的问题是良结构下推系统的表达能力有多强。向量加法系统是一个应用广泛的模型，本文着重研究向量加法系统的三个扩展系统与良结构下推系统的关系。本文将向量加法系统的三种扩展系统以及几个其他模型编码到了良结构下推系统，这些模型上的许多问题可以归约到对应的良结构下推系统上的问题。良结构下推系统的表达能力不低于这些模型。
　　本文的主要贡献有以下三点，通过将导出值的计算转化为顺序计算的过程，给出了分支向量加法系统到良结构下推系统的编码；通过将格局中隐式的栈转化为显示的栈，给出了递归向量加法系统到良结构下推系统的编码；通过将格局向量的一个维度的信息保存在栈深信息中，给出了一位零测试向量加法系统到良结构下推系统的编码。相关的正确性证明也全部给出。以上这三种向量加法系统扩展系统上的可达性问题可以归约到对应的良结构下推系统上的问题。
　　本文还研究了单计数器网络，单计数器自动机，交替向量加法系统等模型，它们也可以编码到良结构下推系统。这些模型上的可达性问题和可覆盖性问题也都可以分别归约到对应的良结构下推系统上的可达性问题和可覆盖性问题。
　　本文的成果对良结构下推系统的进一步研究具有重要的指导意义。良结构下推系统上的可判定性结果可以直接应用在这些可以编码到良结构下推系统的模型上。已经成功地编码到良结构下推系统的这些模型上的可判定性结果，也可以帮助我们探索良结构下推系统其他具有可判定性结果的子类。

目录

封面

声明

中文摘要

英文摘要

目录

主要符号对照表

第一章 绪论

1.1 研究背景

1.2 国内外研究现状

1.3 主要工作与贡献

1.4 章节安排

第二章 背景知识

2.1 数与向量

2.2 字串

2.3 良拟序

2.4 向量加法系统

2.5 迁移系统

2.6 下推系统

2.7 良结构下推系统

第三章 分支向量加法系统到良结构下推系统的编码

3.1 分支向量加法系统的定义

3.2 编码

3.3 编码正确性

3.4 本章小结

第四章 递归向量加法系统到良结构下推系统的编码

4.1 递归向量加法系统的定义

4.2 编码

4.3 编码正确性

4.4 本章小结

第五章 一位零测试向量加法系统到良结构下推系统的编码

5.1 一位零测试向量加法系统的定义

5.2 第一种编码

5.3 第二种编码

5.4 本章小结

第六章 其他模型

6.1 单计数器网络

6.2 单计数器自动机

6.3 交替向量加法系统

6.4 本章小结

第七章 总结与展望

参考文献

致谢

攻读学位期间发表的学术论文目录

攻读学位期间参与的项目