グラフ構造は，複雑な状況を直観的に説明するための基本的な道具として計算機が生まれる前からその構造についての研究や応用が行なわれていました．計算機誕生後は，計算機の内部表現(データ構造)としてプログラム中でグラフが利用されるばかりか，グラフそのものを変換して計算を行なう新しい計算システムなども考案され，従来の静的なグラフ構造の研究(グラフ理論)だけではなく，グラフを操作することに対する性質の変化を究明する研究(グラフ変換理論)が特に重要になっています．また，グラフ変換操作を既存の電子計算機上で実現することを前提にするのではなく，ある種の基本的グラフ変換操作がハードウェア的に実現された計算機を想定してのアルゴリズム構築の視点も必要です．特に近年は，分子計算や量子計算等の自然計算の枠組みでの計算機の立案・設計についても研究が進められており，グラフ変換による計算の基礎理論の必要性が高まっています．

計算機による数式処理は数式を木構造で表現しパターンに適合した部分木を書き換えることにより式の計算や変形を行います．数式中の同一の項を共有するグラフ構造で式を表現しグラフ変換を行うことで計算効率を上げることが可能になります(図1)．そこでは，グラフ構造のパターン照合アルゴリズムや式の意味を変えないグラフ表現方法が重要になります．

グラフ変換は変換計算領域に重複がない限り同時並列計算が可能です．交通網等における最短経路の計算，情報通信ネットワークにおけるネットワーク信頼度の計算，電気回路におけるインピーダンスの計算などには，グラフ変換を利用した計算アルゴリズムが開発されています．変換を利用した計算は変換規則の適用場所や適用順序により計算過程が分岐するため，いつも同じ計算結果が得られるとは限りません(図2)．その計算の分岐が必ず合流することを理論的に証明すること，あるいは，同等の計算を行う必ず合流する変換規則群を導くことが重要になります．

直線状に並んだ頂点をつないだグラフの変形による計算は非線形の物理現象のモデルとして応用されているセルオートマトンによる計算と深く関わりがあります(図3)．セルオートマトンの計算機構を直接実現する素子の可能性として，遺伝子等のDNA鎖を用いた分子計算による実現が考えられています．グラフ変換系やセルオートマトンの計算可能性，計算万能性，計算等価性の判定などの理論は，実現される計算機の能力の有効性を評価します．

グラフ変換の同時並列計算の定式化や計算の合流性の証明には，離散数学，二項関係による関係計算理論，そして，圏論などの代数的手法が必要となります．また，計算能力の評価については，オートマトンや言語理論，計算量の理論，そして，数理論理学が必要となります．理論計算機科学は，現在の電子計算機を効率良く利用するための，データ構造やアルゴリズムの理論だけでなく，新しい計算機構の立案・設計を支援するための理論でもあります．

現在の情報化社会を支える電子計算機の利用技術革新や次世代の新しい計算機構開発を支えるための数学，理論計算機科学の研究を行います．