| 有无1墨水点亚对数空间限定交替式下推自动机之间的关系 |
| |
| 引用本文： | 徐建良,孙剑,陈勇,孟庆春.有无1墨水点亚对数空间限定交替式下推自动机之间的关系[J].中国海洋大学学报(自然科学版),2003,33(3):449-456. |
| |
| 作者姓名： | 徐建良 孙剑 陈勇 孟庆春 |
| |
| 作者单位： | 中国海洋大学计算机科学系,青岛,266071 |
| |
| 摘 要： | 该文引入 1墨水点 2方向交替式下推自动机 ,它是 1个具有额外能力的 2方向交替式下推自动机 ,能够用 1个墨水点在输入带上标记出最多 1个单元格。对具有 1个墨水点的和没有墨水点的亚对数空间限定交替式下推自动机之间的关系进行研究。实例证明了具有 1个墨水点的亚对数空间限定交替式下推自动机的语言受理能力强于没有墨水点的亚对数空间限定交替式下推自动机
|
| 关 键 词： | 交替式下推自动机 亚对数空间限定 交替性 墨水点 |
| 文章编号： | 1001-1862(2002)03-449-08 |
| 修稿时间： | 2002年10月20 |
A Relationship Between Sub-Logarithmic Space-Bounded Alternating Pushdown Automata with and Without 1 Inkdot |
| |
| Xu Jianliang,Sun Jian,Chen Yong,Meng Qingchun.A Relationship Between Sub-Logarithmic Space-Bounded Alternating Pushdown Automata with and Without 1 Inkdot[J].Periodical of Ocean University of China,2003,33(3):449-456. |
| |
| Authors: | Xu Jianliang Sun Jian Chen Yong Meng Qingchun |
| |
| Abstract: | In this paper a 1 inkdot two way alternating pushdown automaton (2apda) is introduced which is a two way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape cell on the input (with an inkdot) once. A relationship between the accepting powers of sub logarithmic space bounded two way alternating pushdown automata with and without 1 inkdot is investigated. It shows that sub logarithmic space bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. |
| |
| Keywords: | alternating pushdown automata sub logarithmic space bounded alternati on inkdot |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
