グラフ変換を用いた計算の単位の定式化と計算量理論の再構築

使用图变换和复杂性理论重构来制定计算单位

• 批准号: 14658093
• 负责人: 溝口 佳寛
• 金额: $ 0.51万
• 依托单位: Kyushu University
• 依托单位国家: 日本
• 项目类别: Grant-in-Aid for Exploratory Research
• 财政年份: 2002
• 资助国家: 日本
• 起止时间: 2002 至 无数据
• 项目状态: 已结题
• 来源: https://kaken.nii.ac.jp/en/grant/KAKENHI-PROJECT-14658093/
• 关键词: グラフ変換; グラフ文法; グラフアルゴリズム

本研究の目的は,(1)グラフ変換を計算の単位としての計算量理論の再構築が可能であるという確信を得るための理論的結果を創造すること.(2)グラフアルゴリズム,グラフ理論,量子計算や分子計算などの新しい計算機のアルゴリズムを研究している人々と交流し少人数でも良いので新しい研究プロジェクトをスタートさせる準備を行うことであった.(1)に関しては,グラフ変換を用いた最短経路問題の新しい解法について,2002年3月(厳密には本申請後,採択前)に次の結果を公表した.Shortest path length calculation using graph transformations, Proc. 6th Joint Conference on Information Sciences, North Carolina, 358-361 (2002).さらに,量子セルオートマトンの一般化に関する結果について,第8回セルオートマトンに関する国際研究集会(2002年9月,プラハ)にて口頭発表した.(2)については,電子メール等による情報交換などをもとに,自分を含め5名による研究グループを構成し,グラフ変換を用いた計算に関する新しいプロジェクトを企画し,科学研究費基盤研究(B)として2002年10月に改めて申請を行った.さらに,この5名を中心に2003年2月に京都市御車会館にて,第5回グラフ書き換え系とその応用ワークショップを開催した.本ワークショップでの主な講演タイトルは,以下の通りである.「グラフ文法におけるAdojoining埋込みの効果」會澤邦夫(島根大学・総合理工学部・教授),「グラフ文法とTutte多項式」山崎浩一(群馬大学・工学部・助教授),「順序木構造パターンの多項式時間機械学習について」正代隆義(九州大学・システム情報科学研究院・助教授),「階層型表に対するグラフ文法」夜久竹夫(日本大学・文理学部・教授),「有限遷移系の木表現式と遷移グラフの自動描画」溝口佳寛(九州大学・数理学研究院・助教授),以上.

The purpose of this study is as follows: (1) to reconstruct the theory of computational quantities by changing the computational units, and to create the theoretical results. (2)The number of people who communicate with each other is small, and the number of people who communicate with each other is small. The number of people who communicate with each other is small, and the number of people who communicate with each other is small. (1)The results of this paper are presented in: Shortest path length calculation using graph transformations, Proc. 6th Joint Conference on Information Sciences, North Carolina, 358-361 (2002). The 8th International Research Conference on Quantum Physics (September 2002) was presented orally. (2)Information exchange among electronic media, etc., is conducted in the following ways: research, organization, research, etc., scientific research, etc., scientific research In February 2003, Kyoto City's Imperial Car Hall opened its fifth edition. The main speech of this article is to discuss the following issues. "The grammar of the game is not easy to use." Kunio Aizawa (Professor, Faculty of Science and Technology, Shimane University),"Grammar and Tutte Polynomials" Koichi Yamazaki (Assistant Professor, Faculty of Engineering, Gunma University),"Sequential tree structure and polynomial time machine learning" Masayoshi Takayoshi (Assistant Professor, Graduate School of Information Science, Kyushu University),"Hierarchical tree structure and polynomial time machine learning grammar" NIKUTAKEO (Professor, Faculty of Arts and Sciences, Nihon University),"Tree expression and migration of finite migration system" Yoshihiro Mizoguchi (Assistant Professor, Graduate School of Mathematics, Kyushu University), above.