On 1-Inkdot Self-Verifying Nondeterministic and Nondeterministic Pushdown Automata with Small Space

摘要：

A relationship between the accepting powers of 1-inkdot nondeterministic and self-verifying nondeterministic pushdown automata with small space is investigated. It is shown that sublogarithmic space-bounded 1-inkdot nondeterministic pushdown automata are more powerful than 1-inkdot self-verifying nondeterministic pushdown automata with the same space.

作者: Jianliang Wang Jianliang Xu

作者单位: College of Information Science and Engineering, Ocean University of China Qingdao, China 266071;Shan College of Information Science and Engineering Ocean University of China Qingdao, China 266071

会议类型: 国际会议

会议名称: Fourth International Conference on Impulsive and Hybrid Dynamical Systems(ICIHDS 2007)(第四届国际脉冲和混合动力系统学术会议)

会议地点: 南宁

会议语种:英文

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