您当前所在位置: 首页 > 学者
在线提示

恭喜!关注成功

在线提示

确认取消关注该学者?

邀请同行关闭

只需输入对方姓名和电子邮箱,就可以邀请你的同行加入中国科技论文在线。

真实姓名:

电子邮件:

尊敬的

我诚挚的邀请你加入中国科技论文在线,点击

链接,进入网站进行注册。

添加个性化留言

已为您找到该学者1条结果 成果回收站

上传时间

2010年06月01日

【期刊论文】A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternationg Pushdown Automata with Only Existential (Universal) States

徐建良, Jian-Liang Xu, Yun-Xia Liu, and Tsunehiro Yoshinaga

J. Comput. Sci. & Technol. Nov. 2006, vol. 21, No.6, pp. 979-983,-0001,():

-1年11月30日

摘要

1-inkodt alternationg pushdown automaton is a slightly mo-dified alternationg pushdown automaton iwht the additional power of marking at most 1 tape-oell on the input (with an inkodt) once. This paper investigates the closute property of sublgarithmic space-bounded 1-inkodt alternationg 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 (logn), the class of sets accepted by weakly (strongly) L (n) space-bounded 1-inkodot two-way alternating pushdown automata with only existential (universal) states not closed under concatnation with regular sets, length-preserving homomrphism, and kleene closure.

alternationg pushdown automata,, 1-inkodot,, sublogarithmic space,, closure property

合作学者