本研究では，高い汎用性をもちながら通常の高水準言語が直接サポートしないグラフ構造を扱うプログラミング言語・モデリング言語のための新たな解析・実装技術の開拓に取り組んだ．対象言語として，階層グラフ書換え言語LMNtal，およびLMNtalのデータ構造をハイパーグラフに拡張したHyperLMNtalをとりあげた．

解析技術については，通常の代数的データ型の範疇を超えるグラフ型の枠組みに対して，型の概念設計および解析の両面から検討を進めた．型の概念設計においては，グラフの書換え規則の型安全性検査を大幅に軽量化する型の差分概念を提案し，型の差分に基づく解析手法の構築を進めた．また，与えられたグラフが型の生成文法から生成できるかどうかの判定にtoken passingの考え方を導入するとともに，tokenの概念を拡張することで，threaded treeのような複雑なグラフ構造の解析が効率良くできることを示した．

実装技術については，まず，木構造よりも低い結合度をもつ非連結グラフ構造も重要な用途をもつことから，非連結構造の書換えの実装最適化に取り組んだ．非連結構造の典型応用はタプルの多重集合の書換えだが，連結グラフのように辺を辿る探索ができないため探索に工夫が必要である．そこで，単調非減少な書換えルールに対して効率的に動作しかつC++等に変換可能なタプル書換えアルゴリズムを提案・評価した．索引構造をはじめとするさまざまな工夫によって，計測例題に対して1000倍以上の高速化に成功した．また，再帰的生成規則で定義したグラフパターンのマッチング機能を備えたCSLMNtal言語について，プログラムの実行過程で繰り返されるパターンマッチングを素朴に実装した場合に発生する重複作業を削減するマッチングアルゴリズムを設計し，実際に計算量が改善されることを確認した．