マージ規則とその適用

語彙 $(V, \langle\!\langle\cdot\rangle\!\rangle)$ のトークン $a, b \in V$ と、$V$ に属さない新しい id $c$ の組 $r = (a, b \mapsto c)$ をマージ規則という。規則 $r$ は語彙を $V' := V \cup \{c\}$、$\langle\!\langle c \rangle\!\rangle := \langle\!\langle a \rangle\!\rangle \langle\!\langle b \rangle\!\rangle$ に広げる。

規則 $r$ の適用 $M_r : V'^{*} \to V'^{*}$ を、列の長さについて再帰的に次で定める。

ここで $u \in V'^{*}$ は残りの列である。すなわち列を左から走査し、$a$ の直後に $b$ があればその 2 個を $c$ 1 個に置き換えて 2 つ進み、そうでなければ 1 つ進む。

トークン列 $x = (t_1, \ldots, t_n)$ について、ペア $(a, b)$ の出現回数を $\mathrm{cnt}_x(a, b) := \#\{ i : 1 \le i < n,\ (t_i, t_{i+1}) = (a, b)\}$、$M_r$ が $x$ の上で行う置き換えの回数を $\mathrm{rep}_r(x)$ と書く。$\mathrm{rep}_r$ は $M_r$ の定義の場合分けに沿って、$\mathrm{rep}_r(\varepsilon) = \mathrm{rep}_r(t_1) = 0$、1 つ目の場合 $\mathrm{rep}_r(t_1t_2u) = 1 + \mathrm{rep}_r(u)$、2 つ目の場合 $\mathrm{rep}_r(t_1t_2u) = \mathrm{rep}_r(t_2u)$ で定まる。