-
29浏览
-
0点赞
-
0收藏
-
0分享
-
73下载
-
0评论
-
引用
期刊论文
A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternationg Pushdown Automata with Only Existential (Universal) States
J. Comput. Sci. & Technol. Nov. 2006, vol. 21, No.6, pp. 979-983,-0001,():
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.
【免责声明】以下全部内容由[徐建良]上传于[2010年06月01日 10时17分13秒],版权归原创者所有。本文仅代表作者本人观点,与本网站无关。本网站对文中陈述、观点判断保持中立,不对所包含内容的准确性、可靠性或完整性提供任何明示或暗示的保证。请读者仅作参考,并请自行承担全部责任。
本学者其他成果
同领域成果