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

点击翻译按钮获取中文摘要

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