Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States

Tsunehiro YOSHINAGA; Katsushi INOUE

Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States

Tsunehiro YOSHINAGA, Katsushi INOUE

Full Text Views

0

Cite this

Summary :

This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTM^k(L(n)) (weak-2UTM^k(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTM^k+1(log log n) - weak-2UTM^k(o(log n)) Ø.

Publication: IEICE TRANSACTIONS on Information Vol.E84-D No.1 pp.61-64

Publication Date: 2001/01/01

Publicized

Online ISSN

DOI

Type of Manuscript: Special Section LETTER (Special Issue on Selected Papers from LA Symposium)

Category

Cite this

Copy

Tsunehiro YOSHINAGA, Katsushi INOUE, "Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States" in IEICE TRANSACTIONS on Information, vol. E84-D, no. 1, pp. 61-64, January 2001, doi: .
Abstract: This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTM^k(L(n)) (weak-2UTM^k(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTM^k+1(log log n) - weak-2UTM^k(o(log n)) Ø.
URL: https://global.ieice.org/en_transactions/information/10.1587/e84-d_1_61/_p

Copy

@ARTICLE{e84-d_1_61,
author={Tsunehiro YOSHINAGA, Katsushi INOUE, },
journal={IEICE TRANSACTIONS on Information},
title={Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States},
year={2001},
volume={E84-D},
number={1},
pages={61-64},
abstract={This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTM^k(L(n)) (weak-2UTM^k(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTM^k+1(log log n) - weak-2UTM^k(o(log n)) Ø.},
keywords={},
doi={},
ISSN={},
month={January},}

Copy

TY - JOUR
TI - Sublogarithmic Space-Bounded Multi-Inkdot Two-Way Alternating Turing Machines with Only Universal States
T2 - IEICE TRANSACTIONS on Information
SP - 61
EP - 64
AU - Tsunehiro YOSHINAGA
AU - Katsushi INOUE
PY - 2001
DO -
JO - IEICE TRANSACTIONS on Information
SN -
VL - E84-D
IS - 1
JA - IEICE TRANSACTIONS on Information
Y1 - January 2001
AB - This paper investigates a hierarchical property based on the number of inkdots in the accepting powers of sublogarithmic space-bounded multi-inkdot two-way alternating Turing machines with only universal states. For each k1 and any function L(n), let strong-2UTM^k(L(n)) (weak-2UTM^k(L(n))) be the class of sets accepted by strongly (weakly) L(n) space-bounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k1, strong-2UTM^k+1(log log n) - weak-2UTM^k(o(log n)) Ø.
ER -