IEICE TRANSACTIONS on Fundamentals
Some Observations on One-way Alternating Pushdown Automata with Sublinear Space
Summary :
This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.
- Publication
- IEICE TRANSACTIONS on Fundamentals Vol.E87-A No.5 pp.1012-1019
- Publication Date
- 2004/05/01
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
- Category
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, Tsunehiro YOSHINAGA, Katsushi INOUE, "Some Observations on One-way Alternating Pushdown Automata with Sublinear Space" in IEICE TRANSACTIONS on Fundamentals,
vol. E87-A, no. 5, pp. 1012-1019, May 2004, doi: .
Abstract: This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.
URL: https://global.ieice.org/en_transactions/fundamentals/10.1587/e87-a_5_1012/_p
Copy
@ARTICLE{e87-a_5_1012,
author={Jianliang XU, Tsunehiro YOSHINAGA, Katsushi INOUE, },
journal={IEICE TRANSACTIONS on Fundamentals},
title={Some Observations on One-way Alternating Pushdown Automata with Sublinear Space},
year={2004},
volume={E87-A},
number={5},
pages={1012-1019},
abstract={This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - Some Observations on One-way Alternating Pushdown Automata with Sublinear Space
T2 - IEICE TRANSACTIONS on Fundamentals
SP - 1012
EP - 1019
AU - Jianliang XU
AU - Tsunehiro YOSHINAGA
AU - Katsushi INOUE
PY - 2004
DO -
JO - IEICE TRANSACTIONS on Fundamentals
SN -
VL - E87-A
IS - 5
JA - IEICE TRANSACTIONS on Fundamentals
Y1 - May 2004
AB - This paper investigates some fundamental properties of one-way alternating pushdown automata with sublinear space. We first show that one-way nondeterministic pushdown automata are incomparale with one-way alternating pushdown automata with only universal states, for spaces between log log n and log n, and also for spaces between log n and n/log n. We then show that there exists an infinite space hierarchy among one-way alternating pushdown automata with only universal states which have sublinear space.
ER -
English
