Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU; Katsushi INOUE; Yue WANG; Akira ITO

Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space

Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO

Full Text Views

0

Cite this

Summary :

This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that lim_n [d (n)log n/n^1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.

Publication: IEICE TRANSACTIONS on Information Vol.E80-D No.12 pp.1221-1226

Publication Date: 1997/12/25

Publicized

Online ISSN

DOI

Type of Manuscript

Category: Automata,Languages and Theory of Computing

Cite this

Copy

Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO, "Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space" in IEICE TRANSACTIONS on Information, vol. E80-D, no. 12, pp. 1221-1226, December 1997, doi: .
Abstract: This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that lim_n [d (n)log n/n^1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.
URL: https://global.ieice.org/en_transactions/information/10.1587/e80-d_12_1221/_p

Copy

@ARTICLE{e80-d_12_1221,
author={Jianliang XU, Katsushi INOUE, Yue WANG, Akira ITO, },
journal={IEICE TRANSACTIONS on Information},
title={Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space},
year={1997},
volume={E80-D},
number={12},
pages={1221-1226},
abstract={This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that lim_n [d (n)log n/n^1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.},
keywords={},
doi={},
ISSN={},
month={December},}

Copy

TY - JOUR
TI - Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
T2 - IEICE TRANSACTIONS on Information
SP - 1221
EP - 1226
AU - Jianliang XU
AU - Katsushi INOUE
AU - Yue WANG
AU - Akira ITO
PY - 1997
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E80-D
IS - 12
JA - IEICE TRANSACTIONS on Information
Y1 - December 1997
AB - This paper first investigates a relationship between inkdot-depth and inkdot-size of inkdot two-way alternating Turing machines and pushdown automata with sublogarithmic space, and shows that there exists a language accepted by a strongly loglog n space-bounded alternating pushdown automaton with inkdot-depth 1, but not accepted by any weakly o (log n) space-bounded and d (n) inkdot-size bounded alternating Turing machine, for any function d (n) such that lim_n [d (n)log n/n^1/2] = 0. In this paper, we also show that there exists an infinite space hierarchy among two-way alternating pushdown automata with sublogarithmic space.
ER -