Sublogarithmic Space-Bounded Multi-Inkdot Tow-Way Alternating Turing Machines with Only Universal States (Special lssue on Selected Papers from LA Synposium)
スポンサーリンク
概要
- 論文の詳細を見る
This paper investigates a hierarchical property based on the number of inkdots in the accepting power of sublogarithmic space-bounded multi-inkdot tow-way alternating Turing machines with only universal states. For each k >__- 1 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) spacebounded k-inkdot two-way alternating Turing machines with only universal states. We show that for each k>__-1, strong-2UTM^<k+1>(loglog n) - weak-2UTM^k(o(log n)) ≐̸ 0.
- 2001-01-01
著者
-
INOUE Katsushi
The authors are with the Department of Computer Science and Systems Engineering, Faculty of Engineer
-
Yoshinaga Tsunehiro
The Author Is With The Depatment Of Computer Science And Electronics Engineering Tokuyama College Of
-
Inoue Katsushi
The Author Is With The Department Of Computer Science And Systems Engineering Faculty Of Engineering
関連論文
- A Note on Sensing Semi-One-Way Simple Multihead Finite Automata (Special lssue on Selected Papers from LA Synposium)
- On the Sensing Function of One-Way Simple Multihead Finite Automata
- Sublogarithmic Space-Bounded Multi-Inkdot Tow-Way Alternating Turing Machines with Only Universal States (Special lssue on Selected Papers from LA Synposium)