インタラクションネット抽象機械の軽量化

• Item type: Trans(1)
• 公開日: 2006-10-15
• タイトル: インタラクションネット抽象機械の軽量化
• タイトル / 言語: en
• タイトル: A Lightweight Abstract Machine for Interaction Nets
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 発表概要
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 姫路獨協大学経済情報学部
• 著者所属: 理化学研究所脳科学総合研究センター
• 著者所属(英): en
• 著者所属(英): Faculty of Econoinformatics, Himeji Dokkyo University
• 著者所属(英): en
• 著者所属(英): RIKEN Brain Science Institute
• 著者名: 佐藤伸也; 杉本, 徹
• 著者名(英): Shinya, Sato; Toru, Sugimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: インタラクションネットは，線形論理を計算的に解釈したグラフ計算体系である．簡約の影響がグラフ全体に及ぶことがなく，さらに，どの順番で相互作用を行っても同じ結果になることから，並列性を持つ計算体系であるといわれている．インタラクションネットの抽象機械も提案されており，その並列実装も実際に行われている．この抽象機械の基本原理には，グラフを項表現によって定式化した項書き換え計算が用いられ，相互作用による接続の変更は変数への代入によって実現されている．このモデルでは項の先頭に名前リストを添え，代入先の捜索を省くようにしているが，それでもまだ接続変更のために多くの操作を必要とする．接続の変更によって相互作用が生じるとは限らないことを考慮すれば，すべての代入操作を行わなくてもよいことが分かる．そこで本発表では，相互作用が後に生じる可能性のある代入操作と，そうでないものに分類し，前者を対象に計算を行えば十分な結果が得られることを示すことにする．これらの操作には名前リストの管理が不要であるため，抽象機械の遷移回数の減少が見込め，計算速度の向上を期待することができる．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Interaction Nets are graphical rewriting systems that can be regarded as a computational interpretation of Linear Logic. In these systems, no rewriting influences the whole graph, and calculation results are the same independent of rewriting order. Therefore Interaction Nets are inherently parallel. An abstract machine for Interaction Nets has been proposed, and it has been implemented as a parallel evaluator. In this machine, Interaction Nets are formulated as a term rewriting system, and a change of connection caused by an interaction is realized by substitutions of variables. Although a list of variables is attached to the head of every term in order to cut down operation of searching for a substitution place, still many operations are needed for a change of connection. Taking into consideration that every change of connection does not cause interactions directly, it turns out that every operation for substitution does not need to be performed eagerly. In this presentation, we divide substitutions into operations that may create new interactions and the others, and we show that it is sufficient to perform the former operations.Since no operation for lists of variables is needed when these operations are performed, we expect to decrease the number of rewritings operations and improve the calculation speed of this machine.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11464814
• 書誌情報: 情報処理学会論文誌プログラミング（PRO）; 巻 47, 号 SIG16(PRO31), p. 89-89, 発行日 2006-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7802
• 出版者 / 言語: ja
• 出版者: 情報処理学会