| Item type |
SIG Technical Reports(1) |
| 公開日 |
2022-05-12 |
| タイトル |
|
|
タイトル |
無向リングにおける無記憶モバイルエージェントの計算能力 |
| タイトル |
|
|
言語 |
en |
|
タイトル |
Computational Power of A Memoryless Mobile Agent in Undirected Rings |
| 言語 |
|
|
言語 |
jpn |
| 資源タイプ |
|
|
資源タイプ識別子 |
http://purl.org/coar/resource_type/c_18gh |
|
資源タイプ |
technical report |
| 著者所属 |
|
|
|
大阪大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
大阪大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
大阪大学大学院情報科学研究科 |
| 著者所属 |
|
|
|
大阪大学大学院情報科学研究科 |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者所属(英) |
|
|
|
en |
|
|
Graduate School of Information Science and Technology, Osaka University |
| 著者名 |
井上, 太智
北村, 直暉
泉, 泰介
増澤, 利光
|
| 著者名(英) |
Taichi, Inoue
Naoki, Kitamura
Taisuke, Izumi
Toshimitsu, Masuzawa
|
| 論文抄録 |
|
|
内容記述タイプ |
Other |
|
内容記述 |
本稿では，????(1) ビットの頂点記憶領域を持つサイズ ???? の匿名な無向リングにおいて，1 体のエージェントが動作するシステムの計算能力について検討する．具体的には，当該のシステム上で動作するエージェントが無記憶である場合と 1 ビットの永続記憶を持つ場合について，後者のエージェントで動作するアルゴリズムを，前者のエージェントが 1 ステップ動作あたり ????(????) 時間のオーバーヘッドでシミュレーションするアルゴリズムを提案することにより，多項式時間求解性の意味で両者の計算能力が等価であることを示す． |
| 論文抄録(英) |
|
|
内容記述タイプ |
Other |
|
内容記述 |
We consider the system where a single mobile agent is deployed in an anonymous, oriented, and undirected ring of ???? vertices with ????(1)-bit storage. We focus on the computational power of this system, in both cases of oblivious agents and non-oblivious agents with one-bit memory. The main contribution of this paper is to show that these two cases are equivalent with respect to the polynomial-time solvability of any given task, by presenting an algorithm of simulating any algorithm for one-bit memory agents by oblivious agents with ????(????)-time overhead per one step simulation. |
| 書誌レコードID |
|
|
収録物識別子タイプ |
NCID |
|
収録物識別子 |
AN1009593X |
| 書誌情報 |
研究報告アルゴリズム（AL）
巻 2022-AL-188,
号 12,
p. 1-8,
発行日 2022-05-12
|
| ISSN |
|
|
収録物識別子タイプ |
ISSN |
|
収録物識別子 |
2188-8566 |
| Notice |
|
|
|
SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc. |
| 出版者 |
|
|
言語 |
ja |
|
出版者 |
情報処理学会 |
IPSJ-AL22188012.pdf (1.7 MB)
