A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
スポンサーリンク
概要
- 論文の詳細を見る
In order to present a technique which we can show that some three-dimensional language is not acceptedby any space-bounded alternating Turing machines, this paper shows that the set of all the cubic input tapes,which each top half part is equal to each bottom half part, is not accepted by any L(m) space-bounded threedimensionalalternating Turing machines for any function L(m) such that lim(m→∞) [L(m)/logm] = 0.
- 2006-08-30
著者
-
FURUTANI Hiroshi
University of Miyazaki
-
Ito Takao
Graduate School of Enginnering, University of Miyazaki
-
Sakamoto Makoto
Dept. of Computer Science and Systems Engineering, University of Miyazaki
-
Saito Makoto
Graduate School of Enginnering, University of Miyazaki
-
Furutani Hiroshi
Dept. of Computer Science and Systems Engineering, University of Miyazaki
-
Kono Michio
Dept. of Computer Science and Systems Engineering, University of Miyazaki
-
Inoue Katsushi
Dept. of Computer Science and Systems Engineering, Yamaguchi University
-
Kono Michio
Univ. Of Miyazaki
-
Inoue Katsushi
Yamaguchi Univ.
-
Sakamoto Makoto
Univ. of Miyazaki
-
Ito Takao
Ube National College of Technology
関連論文
- A Survey of Three-Dimensional Automata
- A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
- Sublinear Space-Bounded One-Way Self-Verifying Nondeterministic Turing Machines
- On Empirical Implications of Highly Interest-Elastic Money Demand : A Note
- One-pot Enantioselectiev Synthesis of Optically Active Homoalylic Alcohols from Allyl Halides
- 空間量が対数以下に制限された存在(全称)状態のみからなる1-インクドット交代チューリングマシンの閉包性について
- IN VIVO ESTIMATION OF PATELLOFEMORAL JOINT CONTACT AREA USING MRI(3B3 Orthopaedic & Rehabilitation Biomechanics VII)
- D-1-1 Three-Dimensional Probabilistic Finite Automata
- Polynomial Time-Bounded Alternating Multi-Counter Automata
- D-1-4 A Relationship between the Accepting Powers of Nondeterministic Finite Automata and Probabilistic Finite Automata on Three-Dimensional Input Tapes
- Effects of α-human atrial natriuretic polypeptide on vascular strips and perfused mesenteric vessels of SHR and WKY