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

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