| 摘要 | 第1-8页 |
| ABSTRACT | 第8-13页 |
| 第一章 绪论 | 第13-25页 |
| 第二章 形式语言与自动机理论基础 | 第25-37页 |
| ·抽象代数中的基本概念和术语 | 第25-27页 |
| ·形式语言与自动机 | 第27-35页 |
| ·字符串和语言 | 第27-28页 |
| ·有穷状态自动机 | 第28-31页 |
| ·图灵机 | 第31-33页 |
| ·下推自动机 | 第33-35页 |
| ·小结 | 第35-37页 |
| 第三章 交替式下推自动机 | 第37-45页 |
| ·定义和记号 | 第37-40页 |
| ·预备性结论 | 第40-44页 |
| ·小结 | 第44-45页 |
| 第四章 多墨水点交替式下推自动机的计算复杂性研究 | 第45-59页 |
| ·定义和记号 | 第45页 |
| ·多墨水点交替式下推自动机的墨水点层次性 | 第45-50页 |
| ·全称状态的计算方式与存在状态的计算方式的不可比较性 | 第50-57页 |
| ·小结 | 第57-59页 |
| 第五章 多墨水点交替式下推自动机的闭包属性 | 第59-71页 |
| ·多墨水点非确定性下推自动机的闭包属性 | 第59-63页 |
| ·仅有全称状态的多墨水点交替式下推自动机的闭包属性 | 第63-68页 |
| ·小结 | 第68-71页 |
| 第六章 交替式下推自动机的闭包属性 | 第71-83页 |
| ·定义和记号 | 第71-72页 |
| ·结果 | 第72-79页 |
| ·小结 | 第79-83页 |
| 第七章 自验证的1墨水点非确定性下推自动机 | 第83-89页 |
| ·定义和记号 | 第83-84页 |
| ·结果 | 第84-88页 |
| ·小结 | 第88-89页 |
| 第八章 总结和展望 | 第89-91页 |
| ·全文的总结 | 第89-90页 |
| ·进一步研究工作展望 | 第90-91页 |
| 参考文献 | 第91-101页 |
| 符号及术语表 | 第101-109页 |
| 致谢 | 第109-110页 |
| 攻读博士学位期间论文完成与发表情况 | 第110-111页 |
| 攻读博士学位期间参加科研情况 | 第111-112页 |
| 个人简历 | 第112页 |