Powered by SmartDoc
(印刷用 PS 版は /home/hattori/visual-prog/latex2e/main.ps です)

グラフ書き換え系の例

項の代わりにグラフを使うと、グラフ書き換え系になる。

Grrrシステム

以下の内容については、資料"Graph Drawing by Graph Rewriting"(/home/hattori/visual-prog/graph-rewriting-{1,2}.ps)を参照。

使用例

ウェブページに載っている例は、二分木を「見やすく」書き直すプログラムであり、基本的なアルゴリズムは次のようになっている。なお、論文に載っている例はもう少し複雑なものである。

  1. 矢印をたどり、それぞれのノードが上から何階層目になっているかを付加する(元のノードと区別するために楕円形のノードを使う)。
  2. 階層ごとにY座標を決定する。
  3. 最下層のノードのX座標を順に決める。
  4. 階層を上がりながら、子ノードの中央に来るように親ノードを動かす。
  5. 作業用に付加したノードを消す。
LayoutTreeに関する書き換え規則

図5.1[LayoutTreeに関する書き換え規則]は、全体の動きを決める書き換え規則である。

  1. 最初に、書き換え対象となるグラフに、LayoutTreeというトリガーを付け加える。
  2. doneYというノードは存在しないので、最初の規則が適用され、doneYというノードとLayoutYというトリガーが新しく出来る。
  3. LayoutYに書き換え規則を適用し、Y座標を決定する。その処理が完了すると、LayoutYは消える。
  4. doneYは存在するので、最初の規則は適用されない。doneXは存在しないので、二番目の規則が適用され、doneXというノードとLayoutXというトリガーが新しく出来る。
  5. LayoutXに書き換え規則を適用し、X座標を決定する。その処理が完了すると、LayoutXは消える。
  6. doneXもdoneYも存在するので、三番目の規則が適用され、LayoutTree, doneY, doneXはすべて消えて、DeleteLevelsというノードが新しくできる。
  7. DeleteLevelsに書き換え規則を適用し、作業用に付加したノードを消す。その処理が完了するとDeleteLevelsも消える。

宿題

Grrrシステムの記法に従って、1からnまでの和を計算する書き換え規則を作れ。ただし、数値計算をするトリガーは、ADDとSUBのみが使えるとする。