具有较小空间复杂性的交替式下推自动机的研究

研究具有较小空间复杂性的交替式下推自动机是非常有意义的，因为交替式下推自动机是一个比交替式图灵机更简单的并行计算模型，它的性质解明对于并行计算机的计算复杂性的研究具有重要意义，很有研究价值。但是关于具有较小空间复杂性的交替式下推自动机的研究在国际和国内都还比较少。本项目将研究两种下推自动机：交替式下推自动机和具有墨水点的交替式下推自动机。我们将围绕亚对数空间和亚线性空间对这两种计算模型的性质展开研究，主要研究内容包括：具有较小空间复杂性的语言族的闭包性的研究、空间复杂性的阶层性的研究、交替深度和交替总量之间的关系以及交替总量的阶层性的研究、具有一个墨水点的交替式下推自动机的基本性质的研究、具有一个墨水点的交替式下推自动机的交替阶层性的研究以及墨水点个数的阶层性问题的研究。