Keyword Search Result

[Keyword] alternation hierarchy(1hit)

1-1hit
  • On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space

    Jianliang XU  Yong CHEN  Tsunehiro YOSHINAGA  Katsushi INOUE  

     
    PAPER-Theory of Automata, Formal Language Theory

      Vol:
    E86-D No:9
      Page(s):
    1814-1824

    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.

FlyerIEICE has prepared a flyer regarding multilingual services. Please use the one in your native language.