On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU; Yong CHEN; Tsunehiro YOSHINAGA; Katsushi INOUE

On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU, Yong CHEN, Tsunehiro YOSHINAGA, Katsushi INOUE

Full Text Views

0

Cite this

Summary :

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.

Publication: IEICE TRANSACTIONS on Information Vol.E86-D No.9 pp.1814-1824

Publication Date: 2003/09/01

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Theory of Automata, Formal Language Theory

Cite this

Copy

Jianliang XU, Yong CHEN, Tsunehiro YOSHINAGA, Katsushi INOUE, "On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space" in IEICE TRANSACTIONS on Information, vol. E86-D, no. 9, pp. 1814-1824, September 2003, doi: .
Abstract: 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.
URL: https://global.ieice.org/en_transactions/information/10.1587/e86-d_9_1814/_p

Copy

@ARTICLE{e86-d_9_1814,
author={Jianliang XU, Yong CHEN, Tsunehiro YOSHINAGA, Katsushi INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space},
year={2003},
volume={E86-D},
number={9},
pages={1814-1824},
abstract={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.},
keywords={},
doi={},
ISSN={},
month={September},}

Copy

TY - JOUR
TI - On 1-Inkdot Alternating Pushdown Automata with Sublogarithmic Space
T2 - IEICE TRANSACTIONS on Information
SP - 1814
EP - 1824
AU - Jianliang XU
AU - Yong CHEN
AU - Tsunehiro YOSHINAGA
AU - Katsushi INOUE
PY - 2003
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E86-D
IS - 9
JA - IEICE TRANSACTIONS on Information
Y1 - September 2003
AB - 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.
ER -