摘要
交替式下推自动机是并行计算的一种模型,它的空间计算复杂性研究对于解明并行算法的内存消耗具有重要意义。复杂性语言族的闭包属性反映了具有一定复杂性空间的并行计算模型之间的组合关系。论文研究仅有全称状态的交替式下推自动机的闭包属性,这些自动机均具有多个墨水点和亚对数限定的存储空间.通过设立巧妙的证人语言,本文使用反证法证明了具有有限多个墨水点的仅有全称状态的交替式下推自动机在星号、保持长度的同态、以及与正则语言的连结等运算下是不封闭的。
Alternating pushdown automaton is a theoretical model of parallel computation which can model the memory consuming of parallel algorithms. The closure properties of complexity classes are used to model combinational relations between parallel computing devices. This paper investigates the closure property of two-way alternating pushdown automata with only universal states which have inkdots and sublogarithmic space. By using the technique of reduction to absurdity, it is shown in this paper that for any function L（n） such that L（n）≥log log n and L（n） =o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded multi-inkdot two-way alternating pushdown automata with only universal states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.
出处
《中国海洋大学学报（自然科学版）》
CAS
CSCD
北大核心
2010年第10期109-112,120,共5页
Periodical of Ocean University of China
基金
国家自然科学基金项目(40806040)资助
