Sublogarithmic Space-Bounded Multi-Inkdot Alternating Pushdown Automata

This thesis is a study of alternating pushdown automata (apda's). Alternation was introduced by Chandra, Kozen and Stockmeyer as a theoretical model of parallel computation. An alternating Turing machine is a generalization of a nondetermin-istic Turing machine whose state set is partitioned into'universal' and 'existential' states. Recently, researches of alternating Turing machines with sublogarithmic space have been advanced. It is valuable to study the properties of apda's with sublogarithmic space, because we believe that the automata can be an instructive model of parallel computation simpler than alternating Turing machines. However, as far as we know, there are few investigations about apda's with sublogarithmic space. From the forgoing reasons, it is natural to investigate the properties of apda's with sublogarithmic space. We introduce two types of machine models, i.e., apda's with sublogarithmic space, and apda's which can use any number of dots of ink, and investigate properties of these automata. This thesis consists of eight chapters.Chapter 1 gives an introduction to some important notions in automata theory, observes a historical overview, and provides a background and a motive for our study.Chapter 2 gives some formal definitions for finite automata, self-verifying au-tomata, Turing machines and pushdown automata. Some important concepts on abstract algebra are also presented in this chapter.Chapter 3 introduces apda's. Some notations and preliminary results used throughout this thesis are also given in this chapter.In chapter 4, we first introduces multi-inkdot two-way apda which has finite number of inkdots. By using inkdot, the machine can markup one cell of the input tape. We first investigate how the number of inkdots influence the accepting power of mulit-inkdot two-way apda, we show that with the increasing on the number of inkdots, the accepting powers of sublogarithmic space-bounded multi-indots 2apda's become stronger, that is, there is an infinite hierarchy on the number of inkdot for multi-inkdot two-way apda's with sublogarithmic space. We then investigate a relationship between sublogarithmic space-bounded multi-inkdot two-way apda's with only universal states and multi-inkdot two-way nondeterministic pushdown automata, we show that the accepting powers of these two kinds of machines are incomparable, this extends the results in [67].In chapter 5, the closure properties of the classes of sets accepted by multi-inkdot apda's, which have sublogarithmic space, are invesitgated. We show that the classes of sets accepted by sublogarithmic space-bounded multi-inkdot two-way apda's with only universal states and the ones with only existential states are not closed under the operations of complementation, concatenation with regular set, Kleene closure, and length-preserving homomorphism. This result extends the result in [68].In chapter 6, we turn to study the closure properties of standard two-way apda's. We show that the classes of sets accepted sublogarithmic space-bounded alternating pushdown automata are not closed under the operations of concatenation, Kleene closure, and length-preserving homomorphism.In chapter 7, we first introduce self-verifying 1-inkdot two-way nondeterministic pushdown automaton which is a self-verifying nondeterministic pushdown automa-ton with 1 inkdot. We show that, with sublogarithmic space, the accepting powers of 1-inkdot two-way nondeterministic pushdown automata are more powerful than those of self-verifying 1-inkdot two-way nondeterministic pushdown automata.Chapter 8 concludes this thesis by summarizing the results and reviewing the problems which have been discussed throughout the study.