%0 Journal Article
%T A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States
%A Jian-Liang Xu
%A Yun-Xia Liu
%A Tsunehiro Yoshinaga
%A <br>Jian-Liang Xu
%A Yun-Xia Liu
%A and Tsunehiro Yoshinaga
%J 计算机科学技术学报
%D 2006
%I 
%X 1-inkdot alternating pushdown automaton is a slightly modified alternating pushdown automaton with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. This paper investigates the closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) states, and shows, for example, that for any function L(n) such that L(n) ≥ log log nn and L(n) = o(log n), the class of sets accepted by weakly (strongly) L(n) space-bounded 1-inkdot two-way alternating pushdown automata with only existential (universal) states is not closed under concatenation with regular sets, length-preserving homomorphism, and Kleene closure. This work is supported by the National Natural Science Foundation of China under Grant No. 60403012.
%K alternating pushdown automata
%K 1-inkdot
%K sublogarithmic space
%K closure property<br>闭包性
%K 串联
%K 计算机技术
%K 自动机器
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=F57FEF5FAEE544283F43708D560ABF1B&aid=BEDF7BCEBFE07985F47313908C0DC069&yid=37904DC365DD7266&vid=659D3B06EBF534A7&iid=B31275AF3241DB2D&sid=CA0B5EEC0BAD621A&eid=88B4027FEBE4F5FF&journal_id=1000-9000&journal_name=计算机科学技术学报&referenced_num=0&reference_num=14