ELCグラフ文法によるMap生成系とその応用の研究

本研究ではMapと云われる族のグラフを形式的に扱うために文字列の形式文法の類似の理論であるグラフ文法を利用することにして、その性質を調べる。研究の段階を追って説明すると次のように進めることができる。(1)Mapの特徴を調べクラスとしての定義を定める。Mapは平面グラフであり応用範囲は広いが、このままでは族として小さく特徴も少ない。それで高次元への拡張を考慮することにする。その際はもはやMapというより胞体と云う言葉が適切である。(2)(1)で定めた族に対してこれに適した生成グラフ文法の族を求める。平面のMapの場合はELC文法とL-システムを併用したものが適切であることが分るが、高次元胞体の場合はこのままでは適切とは云えない。(3)次に幾つかの実験を試みる。公理(開始グラフ)を長方形として(2)で定めた文法の詳細な性質を調べる。例えば、ラベル数と生成されるグラフの同値類の関係などを調べる。平面のMapの場合はある程度の性質が分って来たが、高次元胞体の場合はこのままでは記述法が複雑になりすぎて、よい文法とは云えない。胞体の場合を配慮して文法の定義からやり直す必要がありそうである。(4) Mapの構文解析法とその計算の複雑さの研究もこの種の研究には重要なテーマである。(5)更にこの理論を適用してコンピュータで実際にMapを生成する実験をして実用化を試みる。今年度の段階では平面のMapについては(3)の段階まで実験を続けた。これを数学的に定式化するのが次の課題である。(5)についてはある程度定式化できた所で実験可能であるが(4)(5)とも今後の研究を続ける予定である。

本研究ではMapと云われる族のグラフを形式的に扱うために文字列の形式文法の類似の理論であるグラフ文法を利用することにして、その性質を調べる。研究の段階を追って説明すると次のように進めることができる。(1)Mapの特徴を調べクラスとしての定義を定める。Mapは平面グラフであり応用範囲は広いが、このままでは族として小さく特徴も少ない。それで高次元への拡張を考慮することにする。その際はもはやMapというより胞体と云う言葉が適切である。(2)(1)で定めた族に対してこれに適した生成グラフ文法の族を求める。平面のMapの場合はELC文法とL-システムを併用したものが適切であることが分るが、高次元胞体の場合はこのままでは適切とは云えない。(3)次に幾つかの実験を試みる。公理(開始グラフ)を長方形として(2)で定めた文法の詳細な性質を調べる。例えば、ラベル数と生成されるグラフの同値類の関係などを調べる。平面のMapの場合はある程度の性質が分って来たが、高次元胞体の場合はこのままでは記述法が複雑になりすぎて、よい文法とは云えない。胞体の場合を配慮して文法の定義からやり直す必要がありそうである。(4) Mapの構文解析法とその計算の複雑さの研究もこの種の研究には重要なテーマである。(5)更にこの理論を適用してコンピュータで実際にMapを生成する実験をして実用化を試みる。今年度の段階では平面のMapについては(3)の段階まで実験を続けた。これを数学的に定式化するのが次の課題である。(5)についてはある程度定式化できた所で実験可能であるが(4)(5)とも今後の研究を続ける予定である。