The search functionality is under construction.
The search functionality is under construction.

A Relationship between Two-Way Deterministic One-Counter Automata and One-Pebble Deterministic Turing Machines with Sublogarithmic Space

Tokio OKAZAKI, Lan ZHANG, Katsushi INOUE, Akira ITO, Yue WANG

  • Full Text Views

    0

  • Cite this

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