IEICE TRANSACTIONS on Information
A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
Summary :
This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.
- Publication
- IEICE TRANSACTIONS on Information Vol.E82-D No.5 pp.999-1004
- Publication Date
- 1999/05/25
- Publicized
- Online ISSN
- DOI
- Type of Manuscript
- LETTER
- 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
Tokio OKAZAKI, Lan ZHANG, Katsushi INOUE, Akira ITO, Yue WANG, "A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space" in IEICE TRANSACTIONS on Information,
vol. E82-D, no. 5, pp. 999-1004, May 1999, doi: .
Abstract: This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.
URL: https://global.ieice.org/en_transactions/information/10.1587/e82-d_5_999/_p
Copy
@ARTICLE{e82-d_5_999,
author={Tokio OKAZAKI, Lan ZHANG, Katsushi INOUE, Akira ITO, Yue WANG, },
journal={IEICE TRANSACTIONS on Information},
title={A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space},
year={1999},
volume={E82-D},
number={5},
pages={999-1004},
abstract={This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.},
keywords={},
doi={},
ISSN={},
month={May},}
Copy
TY - JOUR
TI - A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space
T2 - IEICE TRANSACTIONS on Information
SP - 999
EP - 1004
AU - Tokio OKAZAKI
AU - Lan ZHANG
AU - Katsushi INOUE
AU - Akira ITO
AU - Yue WANG
PY - 1999
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E82-D
IS - 5
JA - IEICE TRANSACTIONS on Information
Y1 - May 1999
AB - This paper investigates a relationship between accepting powers of two-way deterministic one-counter automata and one-pebble off-line deterministic Turing machines operating in space between loglog n and log n, and shows that they are incomparable.
ER -
English
