WEKO3
アイテム
A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines
http://hdl.handle.net/10458/452
http://hdl.handle.net/10458/452c8934f3c-5ecc-48ad-9eb7-8341279f4fa6
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00004439527.pdf (513.9 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2007-06-28 | |||||
| タイトル | ||||||
| タイトル | A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | Alternation, Complexity, Computation tree, Configuration, Three-Dimension, Turning Machine | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | departmental bulletin paper | |||||
| その他（別言語等）のタイトル | ||||||
| その他のタイトル | A Space Lower-Bound Technique for Three-Dimensional Alternating Turing Machines | |||||
| 言語 | en | |||||
| 著者 |
Ito, Takao
× Ito, Takao× 坂本, 眞人× Saito, Makoto× Furutani, Hiroshi× Kono, Michio× Inoue, Katsushi |
|||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | In order to present a technique which we can show that some three-dimensional language is not accepted by 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 threedimensional alternating Turing machines for any function L(m) such that lim(m→∞) [L(m)/logm] = 0. |
|||||
| 言語 | en | |||||
| 書誌情報 |
ja : 宮崎大学工学部紀要 en : Memoirs of Faculty of Engineering, University of Miyazaki 巻 35, p. 299-302, 発行日 2006-08-30 |
|||||
| 出版者 | ||||||
| 出版者 | 宮崎大学工学部 | |||||
| 言語 | ja | |||||
| 出版者 | ||||||
| 出版者 | Faculty of Engineering, University of Miyazaki | |||||
| 言語 | en | |||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 05404924 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA00732558 | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
