|
国家科技期刊平台
登录
|
注册
检索
高级检索
相关度
相关度
发表时间
每页显示10条
每页显示10条
每页显示20条
每页显示30条
已找到
2
条结果
有无1墨水点亚对数空间限定交替式下推自动机之间的关系
北大核心
CSCD
CSTPCD
作者：
徐建良
孙剑
陈勇
孟庆春
发表期刊：
青岛海洋大学学报(自然科学版) 2003年3期
关键词：
交替式下推自动机
亚对数空间限定
交替性
墨水点
摘要：
该文引入1墨水点2方向交替式下推自动机,它是1个具有额外能力的2方向交替式下推自动机,能够用1个墨水点在输入带上标记出最多1个单元格.对具有1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究.实例证明了具有1个墨水点的亚对数空间限定交替式下推自动机的语言受理能力强于没有墨水点的亚对数空间限定交替式下推自动机.
亚对数空间限定的多墨水点交替式下推自动机的闭包属性
北大核心
CSCD
CSTPCD
作者：
王建良
徐建良
发表期刊：
中国海洋大学学报（自然科学版） 2010年10期
关键词：
交替式下推自动机
对数以下空间限定
闭包属性
墨水点
摘要：
交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义.复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系.论文研究仅有全称状态的交替式下推自动机的闭包属性,这些自动机均具有多个墨水点和亚对数限定的存储空间.通过设立巧妙的证人语言,本文使用反证法证明了具有有限多个墨水点的仅有全称状态的交替式下推自动机在星号、保持长度的同态、以及与正则语言的连结等运算下是不封闭的.
