We use cookies to improve your experience with our site.
Jian-Liang Xu, Yun-Xia Liu, Tsunehiro Yoshinaga. A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States[J]. Journal of Computer Science and Technology, 2006, 21(6): 979-983.
Citation: Jian-Liang Xu, Yun-Xia Liu, Tsunehiro Yoshinaga. A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States[J]. Journal of Computer Science and Technology, 2006, 21(6): 979-983.

A Note on Non-Closure Property of Sublogarithmic Space-Bounded 1-Inkdot Alternating Pushdown Automata with Only Existential (Universal) States

  • 1-inkdot alternating pushdown automaton is a slightly modifiedalternating pushdown automaton with the additional power of marking atmost 1 tape-cell on the input (with an inkdot) once. This paperinvestigates the closure property of sublogarithmic space-bounded1-inkdot alternating pushdown automata with only existential(universal) states, and shows, for example, that for any functionL(n) such that L(n)>=loglogn and L(n)=o(logn), theclass of sets accepted by weakly (strongly) L(n) space-bounded1-inkdot two-way alternating pushdown automata with onlyexistential (universal) states is not closed under concatenationwith regular sets, length-preserving homomorphism, and Kleene closure.
  • loading

Catalog

    /

    DownLoad:  Full-Size Img  PowerPoint
    Return
    Return