ネットワーク量を計算する並列アルゴリズムに関する研究

网络量计算并行算法研究

• 批准号: 08780296
• 负责人: 溝口 佳寛
• 金额: $ 0.64万
• 依托单位: Kyushu Institute of Technology
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Encouragement of Young Scientists (A)
• 财政年份: 1996
• 资助国家: 日本
• 起止时间: 1996 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-08780296/
• 关键词: ネットワーク; グラフ変換; カテゴリー論; グラフアルゴリズム

本研究の目的は,グラフ変換系の理論的枠組みについての考察を深め,その枠組みの中で新たな有用なネットワーク不変量の発見とその計算アルゴリズム開発,さらに,グラフ変換の特長を生かした並列分散計算手法の開発,及び,理論的解析と実現を考えることである.本年度は以下の通りの実績を修めることが出来た.1.グラフ変換理論における危険対の補題の一般化について変換規則の適用順序を変えても計算結果が変化しないことを保証する危険対の補題について次のような理論的考察を行った.2項関係を用いてグラフとグラフ変換を定式化し,その定式化の中で変換系の危険対の補題が成立することをグラフの圏のプッシュアウトの性質を用いて証明した.木や項を表す制限されたグラフの圏を関係式を用いて定式化した.変換規則を制限することで,それぞれの部分圏でのプッシュアウトが閉じていることを示し,それぞれの制限されたグラフ変換系においても危険対の補題が成立することを示した.本研究特徴は,木や項を表すためのグラフの制限を関係式で形式的に与えていること,危険対の補題の証明を関係計算と圏論の性質だけで抽象的に明解に行っていることである.本成果の一部はThird International Seminar on The use of Relational Methods in Computer Scienceにおいて公表した.2.グラフ変換処理系の実現理論的な形式的グラフ変換体系を取り扱う処理系計算機上へ実現については,プロトタイプとしてグラフ変換のみを行なうシステムの実現と改良を行い実行結果を追試した.変換規則を与える言語を定め汎用の変換システムに拡張すること,グラフアルゴリズムの具体的実現と実行結果の確認を行うことは残念ながら今回は十分には行えなかった.

The purpose of this study is to conduct an in-depth study of the theory of theory, and the analysis of the theory shows that it is useful to improve the calculation of students and students, and to analyze the theory. This year, the following policies will be completed. 1. This is a review of the review of the theory of crisis management, the general theory of crisis management, the general introduction of crisis management, the use of sequential calculation results, the results of sequential calculation, and the review of the review of the theory of secondary training of critical health problems. 2 articles of practice are used to determine the format of the protocol. In the format, you need to know that you are in danger of causing serious problems. The table of the wooden project is limited to the format of the table. In the following rules, you will not be able to do so. If you do not want to do so, you will not be able to do so. The purpose of this study is to provide a clear understanding of the nature of the abstraction in the form of the table of the wooden project, which is in the form of a computer, and in the form of a computer program. This achievement is based on a Third International Seminar on The use of Relational Methods in Computer Science. 2. In the form of an existing theory, the system is based on the data collected from the computer of the computer, and the results of the improved operation are tracked. Following the rules and policies, we need to make sure that we do not know what to do, and that we do not know what to do. In this case, we do not know if we are going to do this.

项目成果

Yoshihiro Mizoguchi: "Properties of Graphs Preserved by Relational Graph Rewritings" Proc.of Third International Seminar on The use of Relational Methods in Computer Science. 83-89 (1997)

Yoshihiro Mizoguchi：“关系图重写保留的图的属性”Proc.of 第三届计算机科学中关系方法的使用国际研讨会。