日本ソフトウェア科学会第 39 回大会 (2022 年度) 講演論文集

マッチング結果の一時保管による非連結グラフ書き換
えの最適化
今川 連

山本 直輝

上田 和紀

プログラミング言語において，ネットワークの構造を抽象化したデータ構造であるグラフを扱えることは重要であり，特に非連結グラフを対象としたパターンマッチングは，閉包の計算や，関係データベース，制約処理等に応用できる．こうしたマッチングでは，連結グラフの場合と異なり，辺を辿って探索を行うことができないため，グラフを多重集合とみなして探索する必要がある．このとき，マッチングの結果として追加される要素をそのまま元の多重集合に追加すると，以降の探索では，既存の要素と新たな要素とを判別することができず，既に試行済みのマッチングを繰り返してしまう可能性がある．そこで，本研究では，新たな要素を別の多重集合に一時的に保存することによって，以前に試行済みのマッチングの反復を避ける手法を提案した．また，非連結グラフを扱えるグラフ書き換え言語である LMNtal の処理系に本手法を実装し，実行時間を削減した．

に含まれる要素はパターンマッチングに成功すると

1 はじめに書き換えられるため，その順序や数などがマッチング

グラフは，インターネットや交通網，人間関係な試行前後で異なる可能性がある．そのため，非連結グ

ど，様々な場所で見られるネットワークの構造を抽象

ラフ書き換えにおいて，愚直にパターンマッチングを化したデータ構造である．グラフ書き換えは，ネット行うと，以前に試行済みのマッチングを繰り返し行っ

ワークの構造を抽象化したデータ構造であるグラフてしまうことがある．

を自然に扱うことができるプログラミングパラダイ
ムである．

そこで本研究では，非連結グラフを扱えるグラフ書
き換え言語である LMNtal [13] を用いて，非連結グラ

グラフ書き換えにおいて，書き換えの対象となる

フ書き換えにおけるいくつかの例題に対する簡単な分グラフは，全ての頂点が辺によって繋がった連結グラ

析，および最適化に関する考察を与え，その最適化のフのみでなく，互いに接続関係を持たない，非連結グ

1 つとして，マッチングの結果として追加される要素

ラフにまで及ぶ．特に，非連結グラフを対象としたパを一時的に別の多重集合に保存することによって以前

ターンマッチングでは，辺を辿った探索が行えないたに施行済みのマッチングの反復を避ける手法を提案，め，グラフを多重集合とみなして探索する必要があ

実装した．

る．また，グラフ書き換えは，パターンマッチングが成功する限り繰り返し行われ，非連結グラフ書き換え

2 非連結グラフマッチングの場合は，対象となる多重集合に対して繰り返し探索

本節では，本論文において着目する非連結グラフが行われると捉えることができる．さらに，多重集合

マッチングについて述べる．特に，連結グラフに対す

Optimizing disconnected graph rewriting by using
temporary storage for matching result
Ren Imagawa, Naoki Yamamoto, Kazunori Ueda, 早稲 田 大 学 基 幹 理 工 学 研 究 科 情 報 理 工・情 報 通 信 専
攻, Dept. of Computer Science and Engineering,
Waseda University.

るマッチングと非連結グラフに対するマッチングの違いを簡単に説明する．
まず，連結グラフ書き換えの例を図 1 に，非連結グ
ラフ書き換えの例を図 2 に示す．頂点はそれぞれ名前を持ち，頂点から伸びる辺（引数）は順序付けられてに要素数が多い場合，同じ要素の組に対するマッチン
グの回数を削減するなど，効率的なマッチングを行う
ような工夫が必要となる．

図1

連結グラフ書き換えの例

3 関連研究
本節では，関連研究・関連言語である，CHR (Con-straint Handling Rules) および RETE について簡単に説明する．

3. 1 CHR (Constraint Handling Rules)
図2

非連結グラフ書き換えの例

CHR は多重集合の書き換えに基づく宣言型の並行制約プログラミング言語である．非連結グラフマッチ

いるとする．

ングは，多重集合の書き換えとも捉えられるため，非

図 1 のグラフはリスト [3,1,2] を表している．リス

常に関連が深い．CHR は独自の言語として動作する

トは，3 引数の ’.’ 頂点を使用して表現する．list

わけでなく，Prolog や Java 等の言語上に実装されたノードはリスト自体の名前を表し，[] ノードはリス

拡張機能として提供される．本論文では，SWI-Prolog

トの終端を表す．図中の ’.’ ノードに記された矢印

上で動作する CHR について説明する．詳細は文献

は第 1 引数の位置を表し，そこから矢印の方向に引[2] [3] を参照されたい．

数が順序付けられることを表す．この例は，リストの3. 1. 1 構文

i 番目の要素が i + 1 番目の要素よりも大きい場合，

CHR の構文を図 3 に示す．CHR には組み込み制

その値を入れ替える書き換えを表している．連結グラ約と CHR 制約の 2 種類の制約が存在する．前者はフに対してマッチングを試す場合，この例では，適当“=” などのホスト言語によって許される制約で，後な ’.’ ノードを 1 つ探し，その接続関係を辿ること

者は CHR プログラムによって定義されるユーザ定でマッチングに必要な頂点を全て探すことができる．

義の制約である．制約は論理変数のとりうる値の関係

一方で，図 2 に示した例では，gcd ノードと整数を表す．例えば，leq(X,Y) と書くと，leq は，変数値を持つ頂点が接続されたグラフが 3 つ存在し，そX, Y の間の何らかの関係を示す制約である．

れぞれのグラフ間には接続関係がない．この例では，また，CHR には Simpliﬁcation rule, Propagation

gcd ノードに整数値が繋がったグラフ 2 つにマッチ

rule, Simpagation rule の 3 種類のルールが存在し，し，Euclid の互減法の 1 ステップを実行する．

CHR プログラムはこれらの有限集合である．図 3 に非連結グラフマッチングにおいては，連結グラフ

示された 3 種類のルールについた r, つまり @ 以前

マッチングのように接続関係を利用した頂点の探索に書かれた部分はルール名を表す．また，E, E1 , E2ができないため，2 つの頂点をそれぞれ独立に探さなは空でない CHR 制約の論理積であり，C は組み込ければならない．この意味で，非連結グラフマッチン

み制約の論理積，G はゴール，つまり，組み込み制

グは多重集合の書き換えとも捉えられる．例えば，図約と CHR 制約の論理積である．

2 の例では，gcd ノードと整数値を持つ頂点が接続さ

図 3 の Simpliﬁcation rule, Propagation rule, Sim-れたグラフを多重集合の要素と捉えることができる．

pagation rule において，ルール左辺の E, E1 , E2 の以上のように，非連結グラフマッチングにおいて部分を ヘッド (Head )，ルール右辺の | より前の C の書き換えルールを繰り返し適用することを考えると，部分をガード (Guard ), | より後の G をボディ(Body)

探索を幾度も繰り返さなければならず，愚直な探索をと呼ぶ．ヘッドは書き換え前の制約の多重集合，ガー行うとマッチングが非効率的になるおそれがある．特ドはヘッドに記述された制約の多重集合が満たすべき

組み込み制約:
CHR 制約:ゴール:
simpliﬁcation rule:propagation rule:simpagation rule:
CHR ルール
CHR プログラム

C, D
E, F
G, H
SR
PR
SP R
R
P
図3

::=
::=
::=
::=
::=
::=
::=
::=

c(t1 , . . . , tn ) | C ∧ D, n ≥ 0e(t1 , . . . , tn ) | E ∧ F, n ≥ 0
C |E |G∧H
r@E ⇔ C | G
r@E ⇒ C | G
r@E1 \E2 ⇔ C | G
SR | P R | SP R
{R1 . . . Rm }, m ≥ 0

CHR の構文規則

条件，ボディは書き換え後の制約の多重集合を表す．

ステムは，プロダクションと呼ばれる If-Then 文のSimpliﬁcation rule はガードの制約 C を満たすヘッ集合から構成される．実行は，ワーキングメモリと呼ド E を ボディ G に書き換える．Propagation rule

ばれるグローバルメモリの現在の内容に対して，どのは ガードの制約 C を満たすヘッド E にマッチする

プロダクションの If 文が満たされるかを判断し，Ifとヘッドは削除せずに，同じ E に対して 1 度のみボ文を満たすプロダクションを 1 つ選び，Then 文を実ディ G を追加する．Simpagation rule は ガードの行することを繰り返すことによって進行する．RETE

制約 C を満たすヘッド E1 , E2 にマッチすると，\ よは，プロダクションシステムにおいて，If 文の集合とり後ろ，つまり E2 をボディ G に書き換える．

要素の集合を，集合を反復することなく比較すること

3. 1. 2 CHR のプログラム例

ができるアルゴリズムである．プロダクションシステ

以下は，SWI-Prolog 上で記述できる CHR の leq

ム自体はグラフを扱うシステムではないが，非連結グ(less than or eual) についてのプログラム例である．

ラフ書き換えは，多重集合書き換えとして捉えられ，:- use_module(library(chr)).
2 :- chr_constraint leq/2.
3 l1@ leq(X,X) <=> true.
4 l2@ leq(X,Y),leq(Y,X) <=> X=Y.
5 l3@ leq(X,Y) \ leq(X,Y) <=> true.
6 l4@ leq(X,Y),leq(Y,Z) ==> leq(X,Z).

その多重集合をルールによって書き換えると考える

1と，集合の要素を集合を反復することなく比較する

RETE は，非連結グラフ書き換えと関連している．

4 LMNtal
最初の行は，CHR を使用する宣言であり，CHR 特
有のコードを書く前に書かなければならない．2 行目
は，CHR を使用する宣言であり，CHR 特有のコードを書く前に書かなければならない．ルール l1 は，leq の 2 つの引数が同じものを指しているならそれを 削除するルールである．l2 は，leq の反対称律を表すルールである．l3 は，全て同じ引数を持つ leq
が 2 つあるとき，1 つを削除するルールである．l4
は，leq の推移律を表し，同じ leq(X,Y),leq(Y,Z)の組について一度だけ leq(X,Z) を追加するルール
である．

3. 2 RETE
RETE [1] は，大量のパターンとオブジェクトを効率よく比較するためのアルゴリズムである．同文献で説明された方法は，プロダクションシステムのインタ
プリタ用に開発されたものである．プロダクションシ

本節では，LMNtal (Linked Multisets of Nodestransformation language) の言語仕様，LMNtal 処
理系について簡単に解説する．詳細は文献 [13] を参照されたい．

4. 1 概要
LMNtal は，階層グラフの書き換えを基とするプロ
グラミング言語である．LMNtal プログラムは，アトム，リンク，ルール，膜の 4 つの構成要素からなる．
アトムはグラフの頂点，リンクはグラフの辺（無向辺）を表す．ルールは，部分グラフの書き換え規則を表現する．膜は，アトム，リンク，ルールを持ち，階層構造を表現する．LMNtal プログラムは，適用可能なルールが存在する限り，そのルールを適用し，部分グラフの書き換えを行う．最終的に，すべてのルールが適用不可能となった場合，プログラムが終了する．

4. 2 構文は，2 価の a アトムのそれぞれの引数の先に int 型のLMNtal の構文規則を図 4 に示す．ここで，P はアトムが繋がっており，X が Y よりも大きいならば，

プロセス，T はプロセステンプレート，Xi はリンク

a(X,Y) を削除し，a(Y,X) を追加するルールである．
uniq($p1 , . . . , $pn ) を使用すると，同型なグラフ構名，p はアトム名と呼ぶ．

LMNtal プログラムにおいて，アトムは小文字か造に対して 1 度のみそのルールを適用させることがら始まる文字列で表現され，リンクは大文字から始ま可能である．uniq 制約をガードに持つルールは，左る文字列で表現される．また，アトムは m(≥ 0) 個の辺にマッチした構造を履歴に保存することによって，順序付けられた引数を持ち，p(X1 , . . . , Xm ) と表す．

その構造に 2 度マッチすることを防ぐ．uniq 制約に

この時，X1 , . . . , Xm はそのアトムに接続されたリン引数を記述しない場合は，そのルール自体を 1 度のク名であり，同じリンク名を引数に持つアトムと接続

み適用させることが可能である．

されていることを表す．さらに，省略構文が存在し，左辺に “\” を記述すると，それより前のアトムは

アトム a の第 n 引数にリンクではなくアトム b を記

書き換えず，後のアトムのみを書き換えることを意味

述すると，アトム a の第 n 引数とアトム b の最終引する．
例えば，プログラム

数のリンクが接続されているものとみなす．m 個のリンクを持つアトムを m 価のアトムと呼び，アトムと引数の数 (価数) の組をファンクタと呼ぶ．アトム

1
2

a(1).
a(X)\:-int(X),uniq(X)| b(X).

には，シンボルアトムとデータアトムの 2 種類が存

は，a(X) を探し，リンク X の先に int 型のアトムが在し，シンボルアトムの場合はアトムの名前が小文字繋がっているとき， 同じ X に対して 1 度のみ b(X)から始まる文字列，データアトムの場合はアトムの名を追加するルールである．このプログラムでは，新た前が整数か浮動小数点か文字列である．

に b(1) が 1 つ生成される．アトム a は削除されな同じリンク名はプロセスの中で高々2 回出現する．
プロセス P の中に 1 度だけ出現するリンク名は P

いため，もし uniq を使わない場合は，b(1) を無限に追加することになりプログラムは停止しない．

の自由リンクと呼び，P の中に 2 度出現するリンク
名は P の局所リンクと呼ぶ．

4. 4 実行時処理系 SLIM
LMNtal ソースコードは，Java によって実装され4. 3 ルール

た LMNtal コンパイラが中間命令列に変換する．変ルールは，左辺 (Head ) に記述されたグラフ構造を，換された中間命令列は，C++言語によって実装され右辺 (Body) に記述されたグラフ構造へと書き換える

た実行時処理系である SLIM が処理し，実行する．詳規則である．また，拡張として，ガード (Guard ) と細は文献 [12] [9] を参照されたい．

呼ばれる制約条件を持つルール構文を以下に示す．なお，r はルールの名前を表す．

r@@ Head :− Guard | Body.

SLIM の実行は，ルール適用可能な部分グラフに対してルールを繰り返し適用し，すべてのルールが適用不可能となったら終了する．

ガ ー ド に は 型 制 約 と ，制 御 構 造 で あ る

SLIM において，アトムは双方向連結リストであuniq($p1 , . . . , $pn ) を記述することができる．型制るアトムリストに格納される．アトムリストはシンボ

約では，型の検査，構造の比較，四則演算を行うこと

ルアトムのファンクタごとに存在する．データアトムができる．扱うことができる型には，unary 型，int

はシンボルアトムのリンクに直接埋め込まれるため，型，ﬂoat 型，ground 型がある．

アトムリストは存在しない．例えば，a(1),b(2,3).

例えば，ガード付きルールが存在した場合，アトムリストは，1 価の a アトムとa(X,Y) :- X > Y | a(Y,X).

2 価の b アトム，についてそれぞれ存在する．

1

アトムを探す際，アトムリストの先頭からアトム

P

T

A

::=
|
|
|
|
::=
|
|
|
|
|
|
|
::=
|

0
p(X1 , . . . , Xm )
P, P
{P }
T :− T0p(X1 , . . . , Xm )
T, T
{T }
T :− T@p$p[ X1 , . . . , Xm |A]p(*X1 , . . . *Xm )
[]
*X
図4

(m ≥ 0)(m ≥ 0)(m > 0)

(空)
(アトム)
(分子)
(セル)
(ルール)
(空)
(アトム)
(分子)
(セル)
(ルール)
(ルール文脈)(プロセス文脈)(アトム集団)(空)(リンク束)

LMNtal の構文規則を取り出し，条件を満たさない場合はバックトラック

る HyperLMNtal ではハイパーグラフを扱えるため，して次のアトムを取り出す．アトムを追加する際は，

CHR の論理変数のように複数の箇所から 1 つのデー

アトムリストの最後尾に追加する．

タを参照する構造を記述することができる．詳細は文献 [7] を参照されたい．

4. 5 CHR との主な違い

このように，LMNtal はグラフを，CHR は制約を

LMNtal と CHR は，多重集合の書き換えを行う

扱うという点と変数が値を持つかという点で異なる．

という点で関連が深く，また，構文の面でも類似して

4. 5. 2 LMNtal uniq と propagation rule

いる．しかしながら，LMNtal と CHR には様々な違

LMNtal の uniq 制約と，CHR の propagation rule

いが存在する．

はマッチング履歴を持ち，履歴に存在するアトム・制

4. 5. 1 扱うデータ

約には高々1 回しかマッチングしないという点で非常LMNtal はグラフ構造を扱う．例えば，a(X), b(X)に似ている．しかしながら，両者の実際の挙動には差はアトム a，b が繋がったグラフを表す．論理変数 X

異がある．LMNtal の uniq は，前述の通り，同型なはリンクを表し，値を持たない．このとき，a, b のグラフ構造に対して高々1 回マッチング成功する．つ両者には対等な関係がある．
一方，CHR は制約を扱う．例えば，a(X), b(X)は，論理変数 X についての制約，a, b が存在するこ

まり，
1
2

a(1),a(1).
a(X) :- uniq(X) | b(X).

とを表す．論理変数 X は値を持つことができる．このようなプログラムを記述した際，2 つの a(1) は同れらを与えた時，以下の 2 つのルールが同時に存在型であるため，ルールは 1 回のみ発火し， b(1) が 1するとする．

つだけ生成される．一方，CHR の propagation rule1
2

r1@ a(A) <=> A=1.
r2@ b(B) <=> B=2.

は，同じ制約の組に対して高々1 回のみマッチング成
功する．つまり，以下の propagation rule を与える

このとき，a(X) について X = 1 であることがルールと，2 つの a(1) は意味は同じであるが，互いに異な

r1 によって導かれるが，b(X) について X = 2 であ

る制約であるため，ルールは 2 回発火し，b(1) が 2

ることも r2 から導かれるため，制約 a(X),b(X) はつ生成される．

矛盾する．そのため，結果として false を返す．

1

LMNtal では CHR のように，値を持つ論理変数を記述することができないが，LMNtal の拡張であa(X) ==> b(X).

に，
1a(1),a(1).

4. 5. 3 操作的意味論

1

LMNtal と CHR にはそれぞれ操作的意味論が存2在する．CHR においては，理論上の操作的意味論と，

43

gcd(3),gcd(27),gcd(30).
g1@@ gcd(0) :-.
g2@@ gcd(M) \ gcd(N):- M=\=0, M=<N, A=N-M | gcd(A).

それを改良した reﬁned operational semantics が定
義されており，実装は reﬁned operational semantics

図5

最大公約数プログラムを基に行われている．一方で，LMNtal において，実装に根差した操作的意味論は存在しない．つまり，

序でマッチングが試されるかを簡単に説明する．ルー

バックトラック等，処理系 SLIM が行う操作を意味

ル g2 は，引数の先に整数アトムが繋がっているよう

論からは議論できない．処理系の操作に根ざした操作

な 2 つの gcd アトム gcd(M), gcd(N) について，M的意味論の定義は，今後の研究課題である．LMNtalの先に繋がった整数が N 以下である場合は，gcd(N)の操作的意味論については文献 [11] を，CHR の操作を削除し，新たに gcd(N-M) を生成する．ルール g1的意味論については文献 [5] を参照されたい．

によって，引数の先に 0 が繋がった gcd アトムが削

4. 5. 4 ルールの実行

除され，最終的に最大公約数が繋がった gcd アトム

LMNtal は，ルールを 1 つ選び，それに対してマッ

1 つが残る．愚直には，どのような順序で探索およびチング可能なアトムをアトムリストから探す．LMN-

書き換えが行われるかを表 1 に示す．ここでは，アtal においては，グラフとルールが階層構造を成すこ

トムリストの中身を gcd アトムに繋がった整数値をとがあるため，この方式を採用しており，これを本論用いて [(3),(27),(30)] のような形で表す．bt はバッ

文において，ルール主導と呼ぶ．

クトラック，fail はルール失敗，succ はルール成功を一方で，CHR は，制約から発火可能なルールを探表す．

す．ある制約が制約ストアに挿入された際，その制約

表 1 のように，アトムリストの先頭からアトムを取はアクティブな制約として，実行可能なルールを探り出して書き換える操作を愚直に繰り返す場合，試すす．その際に，パートナーとなるような制約を探し出

マッチングの量は非常に多くなる．例えば，アトムリ

すことによってマッチングを実現している．これを本ストに n 個のアトムが存在する場合，最悪で n2 通論文において，アトム主導と呼ぶ．

りの組み合わせについてマッチングを試さなければならない．g1 によるアトムの削除が早い段階で行わ5 例題の分析れると，最悪で (n − 1)2 通りを試すことになるため，

非連結グラフマッチングにおいて，マッチングの順

マッチング回数は少なくなる．なお，g2 において，2序やアルゴリズムは，効率に大きな影響を与える．本つのアトムにつながる整数値の差が小さいほど新た

節では，非連結グラフマッチングを行ういくつかの例に生成される gcd アトムに繋がる整数値が小さくな題を提示し，その例題の性質について分析する．まるため，全体のマッチング回数が減る．また，ルール

た，先行研究である CHR は，様々な最適化手法を提を実行する際，アトムリストの先頭から順にアトムを案・実装しており，本節ではその部分についても簡単取り出すため，gcd(M), gcd(N) が同じアトムを参照に触れる．使用する用語については，CHR についてし，必ず 1 回バックトラックを行う．さらに，g2 にも，LMNtal の用語に置き換えて説明する．CHR の

おいて，gcd(M) は削除されないが，愚直な処理系の最適化手法について，詳細については文献 [4] を参照

実装では一度削除され，再度生成される．再度生成されたい．

を行わずアトムを再利用するという方法も考えられ，
この場合 g1 によるアトムの削除は早い段階で行われ

5. 1 最大公約数

ないものの，gcd(3) が常にアトムリストの先頭に存

以下は最大公約数を求めるプログラムの例である．

在することになり，1 回のバックトラックでルールはこのプログラムについて，LMNtal ではどのような順成功する．しかしながら，g2 において，マッチング

表1
ルール
g1
g1
g1
g2
g2
g1
...
g2
g2
g2
g2
g1
...
g2
g2
g1
...
g2
g2
g2
g2
g1
...
g2
g2
g1
...
...
g2
g2
g1
g1
g2
g2
g1
g1
g2

最大公約数プログラムにおけるマッチングの順序
アトム 1
(3)
(27)
(30)
(3)
(3)
(30)
...
(30)
(30)
(30)
(24)
(24)
...
(3)
(3)
(24)
...
(24)
(24)
(24)
(3)
(3)
...
(3)
(3)
(3)
...
...
(3)
(3)
(3)
(0)
(3)
(3)
(0)
(18)
(3)

アトム 2

(3)
(27)
...
(30)
(24)
(3)
(30)
...
(3)
(6)
...
(24)
(3)
(3)
(24)
...
(3)
(21)
...
...
(3)
(3)

(3)
(3)

(3)

アトムリスト[(3),(27),(30)][(3),(27),(30)][(3),(27),(30)][(3),(27),(30)][(3),(27),(30)][(30),(24),(3)]...
[(30),(24),(3)][(30),(24),(3)][(30),(24),(3)][(30),(24),(3)][(3),(6),(24)]...
[(3),(6),(24)][(3),(6),(24)][(24),(3),(3)]...
[(24),(3),(3)][(24),(3),(3)][(24),(3),(3)][(24),(3),(3)][(3),(21),(3)]...
[(3),(21),(3)][(3),(21),(3)][(3),(18),(3)]...
...
[(3),(3),(3)][(3),(3),(3)][(3),(0),(3)][(3),(0),(3)][(3),(3)][(3),(3)][(0),(3)]
[(3)]
[(3)]
[(3)]

動作
bt
bt
fail
bt
succ
bt
...
bt
bt
bt
succ
bt
...
bt
succ
bt
...
bt
bt
bt
succ
bt
...
bt
succ
bt
...
...
bt
succ
bt
succ
bt
succ
succ
fail
fail
ﬁn

の値が繋がっていることが指定されたルールが存在するとき，1 度ルール失敗した後，指定された値が繋がっているアトムが生成されるまでそのルールを試さないような仕組みを作る等の最適化が考えられる．

CHR においては，アトム主導によるマッチングを試すため，1 番目のルールにマッチング失敗したアトムに対して繰り返し 1 番目のルールのマッチングを試してしまうことが無い．また，CHR において，ア
トム主導の仕組みを利用した最適化手法も存在する．

Late Storage は，アトム主導の仕組みを利用した最適化手法の 1 つである．これは，新たに生成されたアトムがルールによって削除される可能性がある場合は直ちにアトムリストに挿入せず，マッチングを試した後，アトムリストに挿入する必要があるときまで挿入を遅らせる手法である．これによって，新たに生成されたアトムがすぐに削除される場合，挿入と削除のコストを削減することができる．
一方で，LMNtal 処理系において，ルール主導であること利用した最適化が考えられる．1 番目のルールについては上で述べた通りである．2 番目のルールについて，ガード部には， M=<N という構造の比較と，A=N-M という四則演算のみが記述されている．

gcd(M) と gcd(N) の 2 つのアトムを探した後，ガード部を満たすか確認するため， M=<N を満たすならそのまま成功，満たさなければ，gcd(M) と gcd(N) を入れ替えることでマッチングが成功する．これは，一般に，
1a(X),a(Y) :- X>Y | Body.

のように，同じファンクタを持つアトム 2 つにマッチする 2 つのアトムの整数値の差が小さいほど全体のマッチング回数が減るため，プログラムや初期状態によって非効率になってしまう場合もあり，アトムの再利用が効率的かどうかは自明ではない．

ングするルールにおいて適用できる．また，
1a(A,B,...),a(C,D,...) :- A>C | Body.

や，
1a(A,B,...),a(C,D,...) :- B>D | Body.

このプログラムにおいて，g1 は，gcd のリンクの先に繋がったデータアトムが 0 であるときのみマッのように，複数個の引数を持つ場合でも，n 番目の引チング成功する．しかしながら，表 1 に示したよう数同士のみを比較している場合にも適用可能である．

に，g2 が成功するたびに全ての 1 引数の gcd アトム
に対してマッチングを試してしまう．そのため，この
例のように，左辺においてアトムのリンクの先に特定

5. 2 グラフアルゴリズム

返すと，既にマッチングに成功したアトムの組に対し

非連結グラフマッチングは，グラフアルゴリズムにてもマッチングを何度も試してしまう可能性がある．

おいても用いられる．以下はその一例で，edge とい

しかし，uniq によって，既にマッチングに成功した

う関係の推移閉包を計算するプログラムである．

アトムの組に対してはマッチングは成功しない．そのため，同じアトムの組み合わせに対してマッチングを

1
2
3

edge(1,2),edge(2,3),edge(3,4).
e1@@ edge(X,Y),edge(Y1,Z) \:- Y=:=Y1, uniq(X,Y,Z) | edge(X,Z).

図6

推移閉包プログラム 1

試さない仕組みを考えることが特に重要になる．第 6
節に示す最適化手法は，この部分に特に関係する手法である．

CHR において，ガード部に存在する Y=:=Y1 に着目し，edge(X,Y) の Y に繋がる値から，パート
ナーとなる edge(Y1,Z) を探す手法が存在する．現

図 6 において，edge アトムには頂点の番号を表す

在 LMNtal 処理系において，データアトムからシン

整数アトムが繋がっており，第 1 引数が表す頂点か

ボルアトムを探すことはできないが，この手法はアトら第 2 引数が表す頂点に向かって辺が張られている

ム主導，ルール主導に関係なく適用可能である．
図 9 は，図 6 の仕様を変更したプログラムである．

ことを意味する．図 6 にはルールがただ 1 つ存在し，
頂点 X から Y への辺と Y1 から Z への辺が存在した
とき，Y が Y1 と等しいなら，同じ X,Y,Z の組について一度だけ X から Z への辺を追加する．このプログラムの初期状態が意味する一般の有向グラフを図 7

1
2
3
4

edge(1,2),edge(2,3),edge(3,4).
p1@@ edge(X,Y) \ :- uniq(X,Y) | path(X,Y).
p2@@ edge(X,Y),path(Y1,Z) \:- Y=:=Y1, uniq(X,Y,Z) | path(X,Z).

に，初期状態として与えるグラフを図 8 に示す．ここで，状態が意味する一般のグラフと，LMNtal の実際

図9

推移閉包プログラム 2のグラフの構造が異なることに注意する必要がある．
状態が意味する一般のグラフは，図 7 に示したよう

図 9 では，初期状態に存在する edge(X,Y) についに有向連結グラフであるが，LMNtal の実際のグラフて，path(X,Y) を追加し，edge(X,Y) と path(Y1,Z)は，図 8 に示したように無向非連結グラフである．

から先ほどと同様のマッチングを試し，マッチングがこのプログラムでは，マッチングに成功しても左辺のアトムが減ることが無いため，ルール適用を繰り成功したら path(X,Z) を追加する．
これらのプログラムは，左辺のアトムが削除されず，また，全てのアトムの組み合わせに対してマッチングを試す必要があるため，初期状態に含まれるアト
ムの数を n，最終状態に含まれるアトムの数を m とすると，図 6 では，最低でも m × m 回マッチングを試す必要がある．図 9 では，edge と path に対して

図7

初期状態が意味する一般のグラフ

マッチングを試すため，それぞれ違うアトムリストからアトムを探すことができ，さらに edge アトムは増えないため，最低 n × m 回のマッチングを試す必要がある．n ≤ m が成り立つため，図 9 は，図 6 と比較し，マッチングの最低回数が少ない．
ここで，図 6 における edge の重複を除いて考える

図8

初期状態として与えたグラフ

とき，図 9 の最終状態が，図 6 において生成されるedge と同様の意味を表す path を含むことを示す（逆は明らかである）．ただし，a, b, c, d, e は整数を表し，

表2

RAM Machine シミュレータの各命令

命令

効果

edge(a,b) のように書いたとき，第 1 引数が a, 第 2

init

A

引数が b と繋がっているようなアトムを表す．この

cnst

B

A

JAK ← Badd

とき，図 6 において，初期状態に含まれないアトムを

A2

A1

JA1 K ← JA1 K + JA2 K

sub

A2

A1

JA1 K ← JA1 K − JA2 Kedge(X,Y) として採用した際に生成可能な edge(X,Z)

mul

A2

A1

JA1 K ← JA1 K ∗ JA2 K

は，初期状態に含まれるアトムを edge(X,Y) として

div

A2

A1

JA1 K ← JA1 K/JA2 K if JA2 K ̸= 0

mov

A2

A1

JA1 K ← JA2 K

採用することによっても生成可能であることを示せ

imv

A2

A1

JA1 K ← J JA2 K K

ば良い．まず，初期状態に含まれず，初期状態同士の

mvi

A2

A1

J JA1 K K ← JA2 K

jmp

L

cjmp

A

マッチングにより生成される edge(a,c) を考えると，初期状態に edge(a,b),edge(b,c) が存在する．この

haltアドレス JAK のレジスタを 0 に初期化

PC ← LLP C ← L if JAK = 0
RAM の計算を停止

ような edge(a,c) を edge(X,Y) として使用し，マッ
チングが成功するとき，edge(c,d) が存在し，新たに

5. 3 RAM Machine シミュレータ

edge(a,d) が生成される．edge(c,d) が存在する時，

以下は，CHR で実装された，プログラムとワーキン

edge(b,c),edge(c,d) によって，edge(b,d) が生成

グメモリからなる RAM (Random Access Memory)

可能である．さらに，edge(a,b),edge(b,d) によっ

Machine のシミュレータ ( [6], Fig. 8) を LMNtal にて，edge(a,d) が生成可能である．また，そのような翻訳したものである．i は命令を表すアトム，m はメedge(a,d) を edge(X,Y) として採用する際，マッチ

モリを表すアトム，c はプログラムカウンタを表す

ングが成功すると，edge(d,e) が存在し，edge(a,e)

アトムである．プログラムは，プログラムカウンタ c

が 1 つ生成される．このような edge(a,e) についてが表す命令 i を実行することにより進行し，値は m

も，edge(b,d),edge(d,e) より edge(b,e) が生成に繋がれる．各命令の効果を示す表を表 2 に示す．な可能で，edge(a,b),edge(b,e) より edge(a,e) が生

お，本表は，文献 [6] の Table I を本プログラムに現成可能である．そのため，新たに生成したアトムをれる命令のみ出現するように修正したものである．

edge(X,Y) として採用する際に生成可能なアトムは，

本例題において，通常，実行したい命令列は複数存初期状態に含まれるアトムを edge(X,Y) として採用

在し，それに伴って格納しておきたい値の数も増加

する際に生成可能なアトムの集合の中に含まれる．こする．そのため，i アトムと m アトムは複数存在すのことから，edge，path が多重集合でなく集合の意

ると考えられる．しかし， c アトムは次に実行する味を持つとすると，推移閉包プログラム 1 の edge と命令の番地を表しており，常に 1 つしか存在しない．

推移閉包プログラム 2 の path は同じ意味を持つとまた，c アトムの引数に繋がる整数が l のとき，第 0いえる．

引数が l に繋がる i アトムを探すことで次に実行す

このように，非連結グラフマッチングにおいて，仕る命令を決定する．そのため，引数の先に繋がったア様の異なるプログラムでも，連結成分の重複を除く場

トムがデータアトムであり，ガード部にデータアトム

合，同じ意味を持つことがある．

同士を比較する等号が含まれているとき，データア

また，uniq(X,Y,Z) ではなく，uniq(X,Z) を記述

トムの情報からアトムを探索することができるようすることによって，ルールによって同じ整数アトムとな仕組みがあれば，より効率的な探索ができる．その繋がった edge アトムを 2 度生成することを防ぐこと

ような仕組みがあるとすると，1 つしか存在しない cができる．

アトムを最初に取得し，そのリンクに繋がった整数ア
トムの値から i アトムを探索することによって，さらに効率の良い探索ができる．
なお，CHR においては，引数の値を用いて制約の

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

i1@@ i(L,init,A),m(A1,B),maxm(M) \ c(L1):- A=:=A1, int(B), L=:=L1, M1=M+1| initm(M1,B,L).
i2@@ initm(A,B,L):- A=<B, A1=A+1| m(A,0), initm(A1,B,L).
i3@@ initm(A,B,L),m(B1,C):- A>B, B=:=B1, int(C), L1=L+1| m(B,0),maxm(B),c(L1).
i4@@ i(L,cnst,B,A) \ m(A1,C),c(L1):- A=:=A1, int(B), int(C),
L=:=L1, L2=L+1| m(A,B), c(L2).
i5@@ i(L,add,B,A),m(B1,Y) \ m(A1,X),c(L1):- A=:=A1, B=:=B1, L=:=L1,
Z=X+Y, L2=L+1| m(A,Z), c(L2).
i6@@ i(L,sub,B,A),m(B1,Y) \ m(A1,X),c(L1):- A=:=A1, B=:=B1, L=:=L1,
Z=X-Y, L2=L+1| m(A,Z), c(L2).
i7@@ i(L,mul,B,A),m(B1,Y) \ m(A1,X),c(L1):- A=:=A1, B=:=B1, L=:=L1,
Z=X*Y, L2=L+1| m(A,Z), c(L2).
i8@@ i(L,div,B,A),m(B1,Y) \ m(A1,X),c(L1):- A=:=A1, B=:=B1, L=:=L1,
Z=X/Y, L2=L+1| m(A,Z), c(L2).
i9@@ i(L,mov,B,A),m(B1,Y) \ m(A1,C),c(L1):- A=:=A1, B=:=B1, int(C), int(Y),L=:=L1, L2=L+1 | m(A,Y), c(L2).
i10@@ i(L,imv,B,A),m(B1,C),m(C1,Y)\ m(A1,D),c(L1):- A=:=A1, B=:=B1, C=:=C1, int(D),int(Y), L=:=L1, L2=L+1| m(A,Y), c(L2).
i11@@ i(L,mvi,B,A),m(B1,Y),m(A1,C)\ m(C1,D),c(L1):- A=:=A1, B=:=B1, C=:=C1, int(D),int(Y), L=:=L1, L2=L+1| m(C,Y), c(L2).
i12@@ i(L,jmp,A) \ c(L1):- int(A), L=:=L1 | c(A).
i13@@ i(L,cjmp,A,J), m(A1,0) \ c(L1):- A=:=A1, int(J), L=:=L1 | c(J).
i14@@ i(L,cjmp,A,C),m(A1,X) \ c(L1):- A=:=A1, L=:=L1, X =\= 0, L2=L+1| c(L2).
i15@@ i(L,halt) \ c(L1) :- L=:=L1 |.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

s1@@ same(P1,P2) \:- int(P1), int(P2), uniq(P1,P2)| same(P2,P1).
s2@@ same(P1,P2) \ same(P3,P4):- P1=:=P3, P2=:=P4 | .
s3@@ school(P1,S1) \ school(P2,S2):- P1=:=P2, S1=:=S2 | .
s4@@ false(P1,S1,S2) \ false(P2,S3,S4):- P1=:=P2, S1=:=S3, S2=:=S4 |.
s5@@ same(P1,P2),same(P3,P4) \:- P1=\=P4, P2=:=P3, uniq(P1,P2,P4)| same(P1,P4).
s6@@ school(P1,S),same(P2,P3) \:- int(S), int(P3), P1=:=P2,
uniq(P1,S,P3)| school(P3,S).
s7@@ school(P1,S1),school(P2,S2) \:- P1=:=P2, S1=\=S2, uniq(P1,S1,S2)| false(P1,S1,S2).

図 11

関係データベースの処理

この例題では，データベースに存在する断片的な情報から推論できる情報を補完し，さらに初期状態に誤りがないかを確かめる．データベースに登録できる
情報は，生徒 p, p1 が同じ学校に所属しているという関係と，生徒 p の学校は s であるという情報である．
それらを same(p,p1 ), school(p,s) で表現している．生徒，学校にはそれぞれ整数の ID が割り当てられており，same，school の各引数のリンクの先にはID を表す整数アトムが繋がっていることとする．生徒は複数の学校には所属できないという制限が存在する．
初期状態には，複数の same アトムと school アト
ムが与えられる．そして，プログラムに示された各操作を行う．s1 は，生徒 p1 と p2 が同じ学校に所属しているならば p2 と p1 が同じ学校に所属していることを表す．s2, s3, s4 は，引数の先に繋がった整数ア
トムの組が等しい 2 つのアトムがあった場合，片方を削除するルールである．s5 は，生徒 p1 と p2 が同

図 10

RAM Machine シミュレータ

じ学校に所属していて，生徒 p3 と p4 が同じ学校に所属しているとき，p2 と p3 が同一人物ならば p1 とを探し出すことができる．

p4 が同じ学校に所属していることを表現するルール
である．s6 は，生徒 p1 が学校 s に所属していて，生

5. 4 関係データベース

徒 p2 と p3 が同じ学校に所属しているとき，生徒 p1

以下は，関係データベースの処理についてのプログと p2 が同一人物であれば，生徒 p3 も学校 s に所属

ラム例である．

していることを表現するルールである．s7 は，生徒

p1 と p2 が同一人物であり，異なる学校 s1 , s2 に所手法が文献 [10] や文献 [8] で提案されたが，依然とし属していることになっているとき，複数の学校に所属てマッチングの重複は起こってしまう．本手法では，してはいけないという条件に反するため，初期状態に

1. ルールの実行順序に非決定性があることを利誤りがあるとして false(p1 ,s1 ,s2 ) を作るルールで

用し，

ある．

2. 生成されるアトムをアトムリストとは別の場所

この例では，複数のルールが相互に関係し，ここに一時的に保管しておくことによってまで紹介した様々なプログラムに出現した形のルー

マッチングの重複を防ぐ．本手法では，マッチングのルが複数出現している．特に，s5, s6, s7 は，図 6, 9

重複を避けるという特性上，左辺に出現するアトムをに含まれるルールと同様の形をしている．s5 は，図削除しないルールに対して特に効果が期待できる．

9 では，左辺の 2 番目と右辺に出現する same アトム

LMNtal は汎用的にグラフを扱うことができる言を別のアトム名に置き換えることによってプログラム

語であるが，記法は単純で，プログラムにアノテーの効率化を行ったが，この例題では，ルール同士が相ションを付けるなど，既存の記法を複雑化するような互に関係し，そのような変更を行うことができるか変更はなるべく行いたくない．さらに，多くの機能を自明でない上，プログラムが複雑化することからも，サポートしていることから，処理系実装の核となる部

そのような変更を行うことは望ましくない．

分の大きな変更はできない．本手法はそのような条件

RAM Machine シミュレータの例題での議論と同にも対応した最適化である．

様に，このプログラムのルールにも整数アトム同士を比較する等号が多数含まれており，引数の先に繋がっ

6. 2 アルゴリズム

た整数アトムの値を使ったアトムの探索を行えること

以下のようなルールについて考える．

が望ましい．

6 マッチング結果の一時保管による最適化
本節では，非連結グラフマッチングにおいて繰り返し適用されるルールに対して，新たに生成されるアト
ムを一時的に本来とは別の場所に保管することによって，以前に試行済みのマッチングの反復を避ける手法を提案する．本手法に対しても，第 2 節において議論したように，非連結グラフマッチングは多重集合の書き換えともみなすことができる．

1

H1 \ H2 :- Guard | B.

ここで，H1 , H2 , B は 0 個以上のアトムの多重集合
であり，Guard は 4. 3 節に示したものと同様である．

H1 の要素数が n であるとすると，各アトムのファン
クタを H1,1 , . . . , H1,n のように表す．H2 についても同様である．

6. 2. 1 従来のアルゴリズム
従来のマッチングのアルゴリズムを Algorithm 1に示す．本来のマッチングではバックトラックを用いたアトムの探索を行っているが，簡単のため，for6. 1 概要
アトムリスト内のアトムに対してルールを繰り返し適用する際に，ルールの適用前後でアトムリスト内のアトムの順序や要素数が変化する場合がある．その場
合，再びマッチングを試す際，以前にマッチングが行われたアトムの組がどれなのかを判断することができない．アトムリスト内の要素は削除されたり，追加されたり，順番が変わったりするため，次にどのアトムから探索を始めるかをルール毎に記憶しておくのも容易ではない．そのようなマッチングの履歴管理を行う

ループを用いて表現している．H1 の要素数を n, H2の要素数を m とする．用語を以下のように定義する．

• Atomlist[F ] : ファンクタ F についてのアトム
リスト• Delete(a1 , . . . , an ) : アトム a1 , . . . , an を削除する関数．

• AddToAtomlist(a1 , . . . , an ) :a1 , . . . , an のk (1 ≤ k ≤ n) 番目のアトムのファンクタをfk としたとき，Atomlist[fk ] にアトム ak を追加する関数．引数に多重集合を記述した場合は，

ングを試すために使用される．

Algorithm 1 従来のマッチング
1: for i1 in Atomlist[H1,1 ] do
2:
...
3:
for in in Atomlist[H1,n ] do4:
for j1 in Atomlist[H2,1 ] do
5:
...
6:
for jm in Atomlist[H2,m ] do
7:
if Guard then8:
Delete(i1 , . . . , in , j1 , . . . , jm )9:
AddToAtomlist(i1 , . . . , in ,B)
10:
return true
11: return false

6. 2. 3 提案手法のアルゴリズム
本手法では，一度アトムリスト内のアトムの全ての組に対してマッチングを試す．生成されるアトムはcurr リストに追加される．削除されるアトムにはフラグが建てられ，即座には削除されず，全ての組に対してマッチングを試した後に削除される．その後，ア
トムリスト内のアトムの全ての組に対してはマッチングが終了しているため，アトムリストと curr リスト
および curr リスト内のみのアトムの組に対してマッ
チングを繰り返し試せば，ルールによって新たに生成されるアトムを含んだ全てのアトムの組に対してマッ

多重集合の各要素を追加する．

チングを試すことができる．しかしこれは，さらにア本アルゴリズムにおいて，true が返されたときルー

トムが追加されることがある可能性を考慮できておルが成功し，1 番目のルールの実行を試し，false がらず，アトムリストと curr リストを使用してマッチ返されたときルールが失敗し，次のルールの実行を試

ングを試した場合，その時に新たに生成されるアトム

す．つまり，true が返され続ける限りプログラムはをさらに別の場所に保管しておく必要がある．その問終了しない．例えばルールが 1 つのみであるような題を解決するため，curr リストはアトムを追加するプログラムにおいては，true が返され続ける限りそ場所としてのみ使用し，アトムリストのアトムの全てのルールを繰り返し実行する．

の組に対してマッチングが終了した後に，curr リス

6. 2. 2 差分アトムリストの導入

トのアトムを prev リストに移動させ，次のマッチン提案手法では，ルールの実行順序には非決定性がグはアトムリストと prev リストのアトムの全ての組あり，どのような順番でルールを実行してもよいことに対して行う．そのマッチングが全て終了したとき，に着目した．ルールが成功したとき，従来の手法ではprev リストのアトムをアトムリストの末尾に移動し，

1 番目に記述されたルールの実行に戻るために全ての

その後 curr リストのアトムを prev リストに移動さループを抜ける必要があった．しかし，本手法では，せる．これを新たなアトムが生成されなくなるまで繰

マッチングに成功した際にもバックトラックによってり返すことによって，ルールによって生成されるアト

次のマッチングを試すことによって，ループを抜けず

ムを含めた全てのアトムの組に対してマッチングを試に単一のルールを可能な限り繰り返し適用する．そのすことができる．

際，アトムリストのアトムは削除してはならず，順序を入れ替えることも許されない．アトムリストに直接本論文で提案する手法のアルゴリズムを Algorithm

2 に示す．用語を以下のように定義する．

アトムを追加すると，最後までバックトラックを行っ• Bits : n + m 桁のビット列てもマッチングを試されていない組が存在する可能性• Bits[k] : Bits の最上位ビットを 1 番目のビットがある．そこで，アトムリストの他に，ルールによって追加されるアトムを一時的に保管しておく，curr
リストと prev リストと呼ばれる 2 本の双方向連結リストを使用する．これらはどちらも，アトムリストと同じ構造を持ち，総称して差分アトムリストと呼ぶ．

curr リストには新たに生成されるアトムが追加され，prev リストは，まだ試していない組に対してマッチとしたときの k 番目のビット• Currlist[F ] : ファンクタ F についての curr リ
スト• Prevlist[F ] : ファンクタ F についての prev リスト• Dellist : 後に削除するアトムを保存しておくリスト• List[0][F ] : Atomlist[F ]• List[1][F ] : Prevlist[F ]• Flag(a1 , . . . , an ) :アトム a1 , . . . , an に削除されたことを示すフラグを立てる関数．

• LateDelete() : Dellist が指すアトムをすべて削除し，Dellist を空にする関数．

• AddToCurrlist(a1 , . . . , an ) : アトム a1 , . . . , anの k (1 ≤ k ≤ n) 番目のアトムのファンクタをfk としたとき，Currlist[fk ] に ak を追加する関数．引数に多重集合を記述した場合は，多重集合の各要素を追加する．

• AddToDellist(a1 , . . . , an ) : アトム a1 , . . . , anの格納位置を Dellist に追加する関数．

• MoveDiﬀatomlist() :Prevlist の ア ト ム を

Atomlist の末尾に移動し，Currlist のアトム
を Prevlist に移動する関数．
同じルールが繰り返し適用できるとき，それ以前にマッチングを試したアトムの組に対してはマッチングを試すことがない．また，ルールの繰り返し適用ができなくなった際，差分アトムリストの中にアトムが存在しないため，本手法を適用しない他のルールに一切の影響を及ぼさない．本手法は，アトムの複製などの操作を行わず，アトムの格納場所を分けることのみによって実現可能であるため，メモリ量がほとんど増加

Algorithm 2 提案手法のマッチング
1: for i1 in Atomlist H1,1 do
2:
...
3:
for in in Atomlist H1,n do
4:for j1 in Atomlist H2,1 do
5:
...
6:
for jm in Atomlist H2,m do
7:
if Guard then8:
Flag(j1 , . . . , jm )9:
AddToDellist(j1 , . . . , jm )10:
AddToCurrlist(B)
11: LateDelete()
12: MoveDiﬀatomlist()
13: if Prevlist is empty then14:
return false
15: while true do
16:
for Bits = 1 to 2n+m − 1 do
17:
for i1 in List[Bits[1]][H1,1 ] do
18:
...
19:
for in in List[Bits[n]][H1,n ] do20:
for j1 in List[Bits[n + 1]][H2,1 ] do
21:
...
22:
for jm in List[Bits[n + m]][H2,m ] do
23:
if Guard then24:
Flag(j1 , . . . , jm )25:
AddToDellist(j1 , . . . , jm )26:
AddToCurrlist(B)
27:
28:
29:
30:

LateDelete()
MoveDiﬀatomlist()
if Prevlist is empty thenreturn true

しない．一方で，他のルールによって追加されたアトムを検知することがないため，一度ルールの繰り返し
適用を終了した後，他のルールでアトムが追加された
場合は，もう一度最初からマッチングを試すことにな

23

e1@@ edge(X,Y),edge(Y1,Z) \:- Y=:=Y1, uniq(X,Z) | edge(X,Z).

る．本手法を適用したルールによって生成されるアト従 来 の 手 法 の マッチ ン グ の 順 序 を 表 3 に ，本ムが他のルールによって使用されないとき，そのアト

手 法 の マッチ ン グ 順 序 を 表 4 に 示 す．こ こ でムに対して，すべてのマッチングを試していることがは ，ア ト ム リ ス ト の 要 素 の 引 数 に 繋 がった 整

保証されているので，本手法を適用したルールは失敗数のタプルをアトムリストの要素として表扱いとして終了することができ，さらなるマッチング

す．例えば，edge(1,2),edge(2,3),edge(3,4) は，の削減ができる．

[(1,2),(2,3),(3,4)] と表す．e1 における edge(X,Y) に対応するアトムをアトム 1，edge(Y1,Z) に対応する

6. 3 手法の適用例

アトムをアトム 2 とし，バックトラック，ルール成功，

図 6 において，同節で示した uniq の改善を含む以ルール失敗の各動作を bt，succ，fail と表す．提案手

下のプログラムについて，従来の手法と本手法での法において，アルゴリズム 2 における 1 行目のループ

マッチングの順序を比較する．

を抜けるときと，16 行目のループにおいて，Bits の1edge(1,2),edge(2,3),edge(3,4).

値をインクリメントするときの動作を next とする．

7. 2 グラフアルゴリズム

マッチングに成功した際の整数の値の組を履歴として (X,Z) の形で表す．なお，このプログラムの唯一

第 5 節に示した推移閉包プログラムに少し変更をのルールは，ルールで作成したアトムが他のルール加えたものについて，実行時間を計測する．推移閉包に使用されることがないため，6. 2. 3 節に示したようプログラム 1 として，LMNtal プログラムのルール

な，失敗扱いで終了する最適化が施されている．

は以下を用いる．

表 3，4 からわかるように，従来の手法では，アトムが追加されるたびにルールが成功終了し，何度も同

123e1@@ edge(X,Y),edge(Y1,Z) \:- int(X), int(Z), Y=:=Y1, uniq(X,Z)| edge(X,Z).

じ組に対してマッチングを試している．また，アトム
リストの先頭からアトムを探す性質上，ルールが最初に取り出すアトムの組は同じアトムを参照してしまっているため，必ずバックトラックする．一方，提案手法では，同じ組に対するマッチングが行われていな
いことがわかる．左辺でアトムを削除しない 1 つのルールのみで構成されるプログラムについて，従来の手法では，アトムリストの中身の順番などに実行時間が左右されるが，提案手法においては，どのような初CHR プログラムのルールは以下を用いる．
1

e2@@ edge(X,Y),edge(Y,Z) ==> edge(X,Z).

推移閉包プログラム 2 として，LMNtal プログラムのルールは以下を用いる．
1
2
3
4
5
6

p1@@ edge(X,Y) \:- int(X), int(Y), uniq(X,Y)| path(X,Y).
p2@@ edge(X,Y),path(Y1,Z) \:- int(X), int(Z), Y=:=Y1, uniq(X,Z)| path(X,Z).

期状態においても，必ず全ての組に対してちょうど 1
回マッチングを試す．
相互に関係する複数のルールが存在するプログラム
や，左辺でアトムを削除するルールについては，マッCHR プログラムのルールは以下を用いる．
1
2

p3@@ edge(X,Y) ==> path(X,Y).
p4@@ edge(X,Y),path(Y,Z) ==> path(X,Z).

チングを試す回数やバックトラックの数は自明ではな

第 5 節で述べたように，推移閉包プログラム 2 は，く，その実行時間については，第 7 節で議論する．

推移閉包プログラム 1 の仕様を変更したものである．

edge と path の重複を除いて考えたとき，推移閉包

7 実行時間プログラム 1 の edge と推移閉包プログラム 2 におけ

本節では，複数の例題の実行時間の計測を行い，結る path は同じ意味を持つ．初期状態として，要素数

果に対する簡単な考察を与える．CHR についても計n としたとき，ある頂点から他の 5 つの頂点へ向かっ測を行うが，CHR の手法に言及する際は，第 5 節とて辺が伸びているようなグラフ ⌊n/5⌋ 個と，ある頂同様に，LMNtal の用語に置き換えて説明する．

点から他の n mod 5 個の頂点へ向かって辺が伸びているようなグラフ 1 個を与える．ただし，i (> 0) 個

7. 1 実行環境

目のグラフの始点となる頂点は，i − 1 個目のグラフ

本節で実行時間を計測したプログラムの実行環境の終点となる頂点うちの 1 つである．そのため，与えを表 5 に示す．

るグラフは，LMNtal では非連結グラフで表現される

各例題について，従来の手法，第 6 節で触れた履歴

ものの，一般的なグラフでは有向連結グラフである．

管理，提案手法，および SWI-Prolog 上の CHR で実以上のような初期状態を与えた時の結果を図 12，

行した際の実行時間を計測する．従来の手法を nor-

13 にそれぞれ示す．

mal，履歴管理を hist，提案手法を diﬀ，SWI-Prolog

図 12，13 の双方について，提案手法は LMNtal に上の CHR を chr とする．LMNtal の各手法についおいて最速である．特に，推移閉包プログラム 2 にて，コンパイルオプションと実行時オプションを表 6

おいて，オーダーが改善されており，提案手法が大に示す．chr については，:-chr option(optimize,

きな効果を示している．また，プログラムの改善に

full). を使用している．

よる効果について，履歴管理にはあまり効果が見ら

表3
アトム 1
(1,2)
(1,2)
(3,4)
(3,4)
(3,4)
(3,4)
(1,3)
(1,2)
(1,2)
(1,2)
(1,2)
(1,3)
(2,3)
(2,3)
(2,3)
(2,3)
(2,3)
(1,2)
...
(3,4)

アトム 2
(1,2)
(2,3)
(3,4)
(1,3)
(1,2)
(2,3)
(3,4)
(1,2)
(2,3)
(1,4)
(1,3)
(3,4)
(1,2)
(2,3)
(1,4)
(1,3)
(3,4)
(1,2)
...
(3,4)

グラフアルゴリズムの例題の従来のマッチング順序
アトムリスト[(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(3,4),(1,3),(1,2),(2,3)][(3,4),(1,3),(1,2),(2,3)][(3,4),(1,3),(1,2),(2,3)][(3,4),(1,3),(1,2),(2,3)][(3,4),(1,3),(1,2),(2,3)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(2,3),(1,4),(1,3),(3,4)][(1,2),(1,4),(1,3),(2,4),(2,3),(3,4)]...
[(1,2),(1,4),(1,3),(2,4),(2,3),(3,4)][(1,2),(1,4),(1,3),(2,4),(2,3),(3,4)]

図 12

履歴

(1,3)
(1,3)
(1,3)
(1,3)
(1,3)
(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4)(1,3),(1,4),(2,4)...
(1,3),(1,4),(2,4)(1,3),(1,4),(2,4)

動作
bt
succ
bt
bt
bt
bt
succ
bt
bt
bt
bt
bt
bt
bt
bt
bt
succ
bt
...
fail
ﬁn

推移閉包プログラム 1 の実行時間

れないが，他の手法については効果がみられる．特は，今回の初期状態においては生成されるアトムの数に，CHR の propagation rule の仕様上，推移閉包は変わらず，影響を及ぼさない．

プログラム 1 の CHR の実行時間は LMNtal と比べてかなり遅くなっていることがわかる．また，uniq

7. 3 関係データベースについて，今回は uniq(X,Z) としたが，これを愚直

第 5 節に示した関係データベースの例題について，に uniq(X,Y,Z) とした場合，改善前のプログラムに実行時間を計測する．LMNtal プログラムのルール

おいて生成されるアトムの数が多くなるため実行時は以下を用いる．

間が増加する．一方で，改善後のプログラムについて1

s1@@ same(P1,P2) \

表4
アトム 1
(1,2)
(1,2)
(1,2)
(2,3)
(2,3)
(2,3)
(3,4)
(3,4)
(3,4)
(1,2)
(1,2)
(2,3)
(2,3)
(3,4)
(3,4)
(1,3)
(1,3)
(1,3)
(2,4)
(2,4)
(2,4)
(1,3)
(1,3)
(2,4)
(2,4)
(1,2)
(2,3)
(3,4)
(1,3)
(2,4)
(1,4)

アトム 2
(1,2)
(2,3)
(3,4)
(1,2)
(2,3)
(3,4)
(1,2)
(2,3)
(3,4)
(1,3)
(2,4)
(1,3)
(2,4)
(1,3)
(2,4)
(1,2)
(2,3)
(3,4)
(1,2)
(2,3)
(3,4)
(1,3)
(1,3)
(1,3)
(2,4)
(1,4)
(1,4)
(1,4)
(1,4)
(1,4)
(1,4)

グラフアルゴリズムの例題の提案手法のマッチング順序

アトムリスト[(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4)][(1,2),(2,3),(3,4),(1,3),(2,4),(1,4)]

図 13

prev リスト
[]
[]
[]
[]
[]
[]
[]
[]
[]
[(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][]

curr リスト[][][(1,3)][(1,3)][(1,3)][(1,3)][(1,3),(2,4)][(1,3),(2,4)][(1,3),(2,4)][][][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)][(1,4)]
[]
[]
[]
[]
[]
[]
[]

推移閉包プログラム 2 の実行時間

履歴

(1,3)
(1,3)
(1,3)
(1,3)
(1,3),(2,4)(1,3),(2,4)(1,3),(2,4)(1,3),(2,4)(1,3),(2,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)(1,3),(2,4),(1,4)

動作
bt
bt
bt
bt
bt
bt
bt
bt
next
bt
bt
bt
bt
bt
next
bt
bt
bt
bt
bt
nt
bt
bt
bt
next
bt
bt
bt
bt
next
fail
ﬁn

表5

実行環境

1

same(P1,P2) ==> same(P2,P1).

OS

Ubuntu18.04

そのため，左辺に same を含むようなルールをいくつCPU

AMD EPYC 7552 48-Core Processor * 2

か追加することによって無限ループが発生しないよう

Memory512Gbyte

LMNtal Compiler

version 1.51

SLIM

version 2.5.0

SWI-Prolog

version 7.6.4 for amd64

なプログラムを実現している．
問題設定として，ある生徒 ID:1 が他のある生徒

ID:2 を招待するとし，そのとき，ID:1 の学校 ID:1 のみがあらかじめわかっているとする．これは，

表6使用したオプション

手法

コンパイル

normal-O3, --slimcode

実行時

-p2

hist

-O3, --slimcode-p2, --history-management

diﬀ

手動で作成

-p2

same(1,2), school(1,-1) で表される．初期状態と√して，same アトムの要素数を n としたとき，⌊ n⌋√
人の生徒がそれぞれ ⌊ n⌋ 人の生徒を招待し，残りを 1 人の生徒が招待することを考える．また，このとき，ある生徒が招待した被招待人と，その次の生徒:- int(P1), int(P2), uniq(P1,P2)| same(P2,P1).
4 s2@@ same(P1,P2) \ same(P3,P4)
5:- P1=:=P3, P2=:=P4 | .
6 s3@@ school(P1,S1) \ school(P2,S2)
7:- P1=:=P2, S1=:=S2 | .
8 s4@@ false(P1,S1,S2) \ false(P2,S3,S4)
9:- P1=:=P2, S1=:=S3, S2=:=S4 |.
10 s5@@ same(P1,P2),same(P3,P4) \11:- P1=\=P4, P2=:=P3, uniq(P1,P2,P4)
12|same(P1,P4).
13 s6@@ school(P1,S),same(P2,P3) \14:- int(S), int(P3), P1=:=P2,
15
uniq(P1,S,P3)
16| school(P3,S).
17 s7@@ school(P1,S1),school(P2,S2) \18:- P1=:=P2, S1=\=S2, uniq(P1,S1,S2)
19| false(P1,S1,S2).

が招待した被招待人が 1 人だけ重複することとする．
√
つまり，全体の要素数は，n + n + k (k = 0 or 1) にCHR のプログラムは以下を用いる．

全てのルールが一度適用されると適用不能になるまで

2

3

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

s8@@ same(P1,P2) \ same(P1,P2) <=> true.
s9@@ school(P1,P2) \ school(P1,P2) <=> true.
s10@@ false(P1,S1,S2) \ false(P1,S1,S2)<=> true.
s11@@ same(P1,P2),same(P2,P3)==> P1=\=P3 |same(P1,P3).
s12@@ same(P1,P2),same(P1,P3)==> P2=\=P3 | same(P2,P3).
s13@@ same(P1,P2),same(P3,P2)==> P1=\=P3 | same(P1,P3).
s14@@ school(P1,S),same(P1,P2)==> school(P2,S).
s15@@ school(P1,S),same(P2,P1)==> school(P2,S).
s16@@ school(P1,S1),school(P1,S2)==> S1=\=S2 | false(P1,S1,S2).

なるが，単に初期状態の要素数を表す際，ここでは，

same アトムの数を意味することとする．
以上のような初期状態を与えたときの結果を図 14に示す．
図 14 より，LMNtal の手法の中で，提案手法は最速であることがわかる．しかしながら，第 6 節で述べたように，提案手法は複数ルールにまたがる最適化をしないため，このような問題においては一度実行されたあるルールについて，他のルールが適用されるともう一度全ての組に対してマッチングを試してしまう．
続けて適用されるため，今回の例では，ルール s1 →s2 → s5 → s1 → s2 → s6 → s3 → s7 → s4 の順で適用され，プログラムが終了する．重複したアトムを削除するルールは比較的早い段階で実行されるため，後に削除されるアトムに対して何度もマッチングを試してしまうようなことは防がれている．そのため，

LMNtal の他の手法と比較すると，提案手法は高速である．
一方で，CHR においては，ルールを超えた分析と最適化がなされている．例えば，CHR プログラムのルール s8, s9, s10 のように，重複したアトムを削除

なお，CHR において，LMNtal のルール s1 に対応すするようなルールがあると，それを格納しておく場所

る以下の propagation rule は，uniq と propagation

は多重集合ではなく集合の意味を持つことがわかる．

rule の仕様の違いから，無限ループを引き起こす．

集合の意味を持つアトムをアトムリストに追加する

図 14

データベースの例題の実行時間

際，同じアトムが既にアトムリストに存在する場合は• 3 の倍数を降順に与えたとき追加しない．また，これまで議論したように，アトムの 2 つの初期状態についてそれぞれ計測した結果を．

主導での探索を行っていることや，引数の値からアト

図 15，16 にそれぞれ示す．

ムを探すことができることから，LMNtal と比較し効率の良い探索ができている．

従来の手法や履歴管理では，gcd(0) が出現すると，直ちに g1 によってそれが削除される．しかしながら，ルール主導での探索を行っている LMNtal 処理系

提案手法では，g2 が一度適用されると，それが適用においても，例えば，あるルールの左辺に出現するア可能である限り g2 の適用をしてしまうため，削除は

トムが他のルールの右辺で生成されるという情報は最後にまとめて行われる．また，初期状態を昇順に与コンパイル時に解析できる．そのため，あるルール

えた場合，gcd(3) がアトムリストの先頭に存在し，

r の実行を一通り試した後は，r の左辺に出現するア

他のアトムはすべて 3 以上の数を引数として持つた

トムが他のルールによって追加されるまで，ルール r

め，提案手法では，最悪の順序でマッチングが行われの適用を再び試さないという最適化が考えられる．こる．そのため，図 15 を見ると，提案手法は他の手法の最適化のアイデアは，今回の提案手法に対してはよりも実行時間オーダーが劣っており，これについて

ルールを一度実行した後に適用可能であり，それ以外は適用すべきではないといえる．

の LMNtal の手法に対しては，一度ルール失敗した後に適用可能である．

一方で，初期状態を降順に与えた場合，最悪の順序でのマッチングは防げる．しかしながら，gcd(0) となったアトムを直ちに削除できないという欠点は残さ

7. 4 最大公約数

れており，図 16 を見ても，他の手法より優れている

最大公約数を求めるプログラムについて，実行時とは言えない．

間を計測する．LMNtal プログラムのルールは，図 5から初期状態を除いたものを用いる．CHR プログラ

そのため，最大公約数を求める問題の特性上，本手法は適用すべきではないことがわかる．

ムのルールは以下を用いる．
1
2
3

g3@@ gcd(0) <=> true.
g4@@ gcd(M) \ gcd(N)<=> M=<N, A is N-M | gcd(A).

• 3 の倍数を昇順に与えたとき8 まとめと今後の課題
非連結グラフ書き換えはさまざまな例題を扱うことができることを示し，またその例題に対してグラフ

図 15

最大公約数を求めるプログラムに初期状態として 3 の倍数を昇順に与えたときの実行結果

図 16

最大公約数を求めるプログラムに初期状態として 3 の倍数を降順に与えたときの実行結果

書き換え言語 LMNtal を用いて分析，考察を与えた．

8. 1 データアトムを使ったアトムの探索

さらに，その最適化の 1 つとして，繰り返し適用さ本論文で示したように，非連結グラフマッチングにれるルールに対して，マッチング結果を一時的に本来おいて，アトムの引数につながる整数値を比較する等とは別の場所に保存しておくことによって重複した

号は多く用いられる．そのような情報をアトムの探索

マッチングを防ぐ手法を提案した．本手法によって，に使用できるような仕組みを作ることは，最適化の課

非連結グラフ書き換えの実行時間の削減に成功した．

題として残されている．

しかしながら，問題の特性によっては適用不可能な例
題も存在することに注意する必要がある．また本手法

8. 2 複数のルール間をまたがる最適化

は，単一の繰り返し適用されるルールに対する最適化

第 7 節で示したように，ルール r を一通り実行しであり，以下に述べるような最適化が残されている．

た後，r の左辺に出現するアトムが他のルールによって追加されるまで，r は再び実行しないようにするといった複数ルールをまたがる最適化が残されている．

参 考 文 献これは，アトム主導であれば，アトムに対して適用可[ 1 ] Forgy, C. L.: Rete: A fast algorithm for the
many pattern/many object pattern match problem,
Artiﬁcial Intelligence, Vol. 19, No. 1(1982), pp. 17–37.
[ 2 ] Frühwirth, T.: Constraint Handling Rules,
Cambridge University Press, 2009.
[ 3 ] Frühwirth, T. and Raiser, F.: Constraint Handling Rules: Compilation, Execution, and Analysis,
Books On Demand GmbH, 2011.
[ 4 ] Holzbaur, C., de la Banda, M. G., Jeﬀery,D., and Stuckey, P. J.: Optimizing Compilationof Constraint Handling Rules, Logic Programming,
Codognet, P.(ed.), Berlin, Heidelberg, Springer
Berlin Heidelberg, 2001, pp. 74–89.
[ 5 ] Schrijvers, T.: Analyses, Optimizations and Extensions of Constraint Handling Rules, PhD Thesis,
KATHOLIEKE UNIVERSITEIT LEUVEN, 2005.
[ 6 ] Sneyers, J., Schrijvers, T., and Demoen, B.:
The Computational Power and Complexity of Constraint Handling Rules, ACM Trans. Program.
Lang. Syst., Vol. 31, No. 2(2009).
[ 7 ] Ueda, K. and Ogawa, S.: HyperLMNtal: An
Extension of a Hierachical Graph Rewriting Model,Künstliche Intelligenz, Vol. 26, No. 1(2012).
[ 8 ] 村山敬: 計算量が予測可能な LMNtal システムの設計と実装, 修士論文, 早稲田大学理工学研究科情報・ネッ
トワーク専攻, 2007.
[ 9 ] 後町将人, 堀泰祐, 上田和紀: LMNtal 実行時処理系の並列モデル検査器への発展, コンピュータソフトウェ
ア, Vol. 28, No. 4(2011), pp. 4 137–4 157.
[10] 中田昌輝: グラフ書き換え言語 LMNtal における非連結サブパターンマッチング高速化手法, 卒業論文, 早稲田大学基幹理工学部情報理工学科, 2021.
[11] 上田和紀, 加藤紀夫: 言語モデル LMNtal, コン
ピュータソフトウェア, Vol. 21, No. 2(2004).
[12] 石川力, 堀泰祐, 村山敬, 岡部亮, 上田和紀: 軽量なLMNtal 実行時処理系 SLIM の設計と実装, 情報処理学会第 70 回全国大会講演論文集, (2008), pp. 153–154.
[13] 乾敦行, 工藤晋太郎, 原耕司, 水野謙, 加藤紀夫, 上田和紀: 階層グラフ書換えモデルに基づく統合プログラミ
ング言語 LMNtal, コンピュータソフトウェア, Vol. 25,
No. 1(2008), pp. 1 124–1 150.

能なルールを探すという特性上自動的に行われることであるが，LMNtal はルール主導を採用しているため，処理系の開発側で工夫しなければならない部分
である．

8. 3 コンパイラへの実装
本手法は，LMNtal コンパイラには実装されていない．また，本手法は全ての非連結グラフマッチングに対して汎用的な手法ではないことが第 7 節で示された．そのため，どのようなルールに対してこの最適化が有効であるかコンパイラが判断できる必要がある．また，最大公約数を求めるプログラムのように，初期状態によって実行時間が大きく変わる問題も存在する．これは，複数のルールの関係性を分析しなければならず，複数のルールの関係性について汎用的な分析を与えるのは，非連結グラフマッチング全体の課題である．
謝辞 LMNtal の研究開発に携わる早稲田大学上田研究室の皆様に感謝します．特に，様々な助言をいた
だきました佐野仁氏，実装に関するサポートをしていただいた田口智大氏，同研究室をご卒業された後にも関わらず助言を頂いた中田昌輝氏に感謝します．本研
究の一部は，早稲田大学特定課題研究費 (2022C-421,

2022Q-006) の補助を得て実施しました．