亚对数空间限定的多墨水点交替式下推自动机的闭包属性

• 作者: 徐建良 王建良
• 来源期刊: 中国海洋大学学报（自然科学版）
• 学科: 工学
• 关键词: 交替式下推自动机 对数以下空间限定 闭包属性 墨水点
• 年，卷（期）: 2010,（10）
• 页码范围: 109-112,120
• 分类号: TP301.2
• 字数: 4893字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-5174.2010.10.020

摘要

交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义.复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系.论文研究仅有全称状态的交替式下推自动机的闭包属性,这些自动机均具有多个墨水点和亚对数限定的存储空间.通过设立巧妙的证人语言,本文使用反证法证明了具有有限多个墨水点的仅有全称状态的交替式下推自动机在星号、保持长度的同态、以及与正则语言的连结等运算下是不封闭的.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	徐建良	中国海洋大学信息科学与工程学院	54	216	8.0	11.0
2	王建良	山东交通职业学院管理与信息学院	6	10	2.0	3.0