On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU  Yong CHEN  Tsunehiro YOSHINAGA  Katsushi INOUE  

IEICE TRANSACTIONS on Information and Systems   Vol.E86-D   No.9   pp.1814-1824
Publication Date: 2003/09/01
Online ISSN: 
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)>>
Buy this Article

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.