IEICE TRANSACTIONS on Information
Some Observations Concerning Alternating Pushdown Automata with Sublogarithmic Space
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 limn
- 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
Authors
Keyword
Latest Issue
Copyrights notice of machine-translated contents
The copyright of the original papers published on this site belongs to IEICE. Unauthorized use of the original or translated papers is prohibited. See IEICE Provisions on Copyright for details.
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 limn
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 limn
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 limn
ER -
English
