Some Observations On Multi-lnkdot Alternating Pushdown Automata

This thesis is a study of k-inkdot two-way alternating pushdown automata ( 2APDA* ).The k-inkdot alternating pushdown automata is a two-way alternating pushdown automata with the additional power of marking at most k tape-cells on the input (with k inkdots). These tape-cells are marked once and for all (no erasing). Chandra, Kozen and Stockmeyer introduced alternation as a theoretical model of parallel computation. An alternating Turing machine M is a generalization of a nondeterministic Turing machine, whose state set is partitioned into'universal'and'existential'states.Recently, researchers of alternating Turing machines with sub- logarithmic space have been advanced.It is worthwhile to investigate the properties of two-way alternating pushdown automata (2APDA) with sublogarithmic space, because we think that these automata can be instructive models of parallel computation which are simpler than alternating Turing machines. However, as far as we know, there are few investigations about alternating pushdown automata with small space (especially, with sublogarithmic space). This paper mainly investigates:(I) a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating pushdown automata with only universal states.(II) closure property of sublogarithmic space-bounded 1-inkdot alternating pushdown automata with only existential (universal) states.The paper consists of 7 parts as follows.