WEKO3
アイテム
Some Properties of Multihead Automata on Four-Dimensional Input Tapes
http://hdl.handle.net/10458/2422
http://hdl.handle.net/10458/24222f7f4d7b-ae08-4f81-8a49-f329d13382a2
| 名前 / ファイル | ライセンス | アクション |
|---|---|---|
KJ00005633659.pdf (806.4 kB)
|
|
| Item type | 紀要論文 / Departmental Bulletin Paper(1) | |||||
|---|---|---|---|---|---|---|
| 公開日 | 2009-10-30 | |||||
| タイトル | ||||||
| タイトル | Some Properties of Multihead Automata on Four-Dimensional Input Tapes | |||||
| 言語 | en | |||||
| 言語 | ||||||
| 言語 | eng | |||||
| キーワード | ||||||
| 言語 | en | |||||
| 主題Scheme | Other | |||||
| 主題 | computational complexity, finite automaton, four-dimension, multihead, path-bounded | |||||
| 資源タイプ | ||||||
| 資源タイプ識別子 | http://purl.org/coar/resource_type/c_6501 | |||||
| 資源タイプ | departmental bulletin paper | |||||
| 著者 |
Fukuda, Masatsugu
× Fukuda, Masatsugu× Okatani, Satoshi× 坂本, 眞人 |
|||||
| 抄録 | ||||||
| 内容記述タイプ | Abstract | |||||
| 内容記述 | The comparative study of the computational powers of deterministic and nondeterministic computations is one of the central tasks of complexity theory. This paper investigates the computational power of nondeterministic computing devices with restricted nondeterminism. There are only few results measuring the computational power of restricted nondeterminism. In general, there are three possibilities to measure the amount of nondeterminism in computation. In this paper, we consider the possibility to count the number of different nondeterministic computation paths on any input. In particular, we deal with seven-way four-dimensional finite automata with multiple input heads operating on four-dimensional input tapes. | |||||
| 言語 | en | |||||
| 書誌情報 |
ja : 宮崎大学工学部紀要 en : Memoirs of Faculty of Engineering, University of Miyazaki 巻 38, p. 341-344, 発行日 2009-09-30 |
|||||
| 出版者 | ||||||
| 出版者 | 宮崎大学工学部 | |||||
| 言語 | ja | |||||
| 出版者 | ||||||
| 出版者 | Faculty of Engineering, University of Miyazaki | |||||
| 言語 | en | |||||
| ISSN | ||||||
| 収録物識別子タイプ | ISSN | |||||
| 収録物識別子 | 05404924 | |||||
| 書誌レコードID | ||||||
| 収録物識別子タイプ | NCID | |||||
| 収録物識別子 | AA00732558 | |||||
| 著者版フラグ | ||||||
| 出版タイプ | VoR | |||||
| 出版タイプResource | http://purl.org/coar/version/c_970fb48d4fbd8a85 | |||||
