Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Pushdown Automata with Only Universal States

摘要：

A hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating pushdown automata with only universal states is investigated. For these automata, it is shown that k +1 inkdots are better than k inkdots for each k≥1.

作者: Jianliang Xu Jianjun Xu

作者单位: Department of Computer Science Ocean University of China Qingdao 266071, China

会议类型: 国际会议

会议名称: 第三届国际脉冲动力系统及应用学术会议

会议地点: 青岛

会议语种:英文

在线出版日期: 2006-07-21（万方平台首次上网日期，不代表论文的发表时间）