For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space
Jianliang XU Yong CHEN Tsunehiro YOSHINAGA Katsushi INOUE
IEICE TRANSACTIONS on Information and Systems
Publication Date: 2003/09/01
Print ISSN: 0916-8532
Type of Manuscript: PAPER
Category: Theory of Automata, Formal Language Theory
alternating pushdown automata, 1-inkdot, alternation hierarchy, sublogarithmic complexity,
Full Text: PDF(298.1KB)>>
This paper introduces a 1-inkdot two-way alternating pushdown automaton which is a two-way alternating pushdown automaton (2apda) with the additional power of marking at most 1 tape-cell on the input (with an inkdot) once. We first investigate a relationship between the accepting powers of sublogarithmically space-bounded 2apda's with and without 1 inkdot, and show, for example, that sublogarithmically space-bounded 2apda's with 1 inkdot are more powerful than those which have no inkdots. We next investigate an alternation hierarchy for sublogarithmically space-bounded 1-inkdot 2apda's, and show that the alternation hierarchy on the first level for 1-inkdot 2apda's holds, and we also show that 1-inkdot two-way nondeterministic pushdown automata using sublogarithmic space are incomparable with 1-inkdot two-way alternating pushdown automata with only universal states using the same space.