A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential （Universal） States

1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input （with an inkdot） once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential （universal） states, and shows, for example, that for any function L（n） such that L（n） ≥ log logn and L（n） = o（log n）, the class of sets accepted by weakly （strongly） L（n） space-bounded 1-inkdot two-way alternating pushdown automata with only existential （universal） states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure.

有无1墨水点亚对数空间限定交替式下推自动机之间的关系

该文引入 1墨水点 2方向交替式下推自动机 ,它是 1个具有额外能力的 2方向交替式下推自动机 ,能够用 1个墨水点在输入带上标记出最多 1个单元格。对具有 1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究。实例证明了具有

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

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