DocumentCode
2451578
Title
Sublogarithmic Space-bounded Multi-inkdot Alternating Pushdown Automata with Only Existential (Universal) States
Author
Xu Jian-Liang ; Wang Jian-liang
Author_Institution
Dept. of Comput. Sci. & Technol., Ocean Univ. of China, Qingdao, China
fYear
2009
fDate
25-26 April 2009
Firstpage
750
Lastpage
753
Abstract
This paper investigates some properties of two-way alternating pushdown automata with only existential (universal) states which have inkdots and sublogarithmic space. We show, for example, that for sublogarithmic space-bounded computations, multi-inkdot two-way alternating pushdown automata with only existential states are incomparable with the ones with only universal states, and the classes of sets accepted by these pushdown automata are not closed under complementation.
Keywords
pushdown automata; multiinkdot alternating pushdown automata; sublogarithmic space-bounded computation; Artificial intelligence; Automata; Computational modeling; Computer science; Concurrent computing; Marine technology; Oceans; Paper technology; Space technology; Turing machines; alternating pushdown automata; closure property; incomparability; multi-inkdot; sublogarithmic space;
fLanguage
English
Publisher
ieee
Conference_Titel
Artificial Intelligence, 2009. JCAI '09. International Joint Conference on
Conference_Location
Hainan Island
Print_ISBN
978-0-7695-3615-6
Type
conf
DOI
10.1109/JCAI.2009.151
Filename
5159112
Link To Document