Kleene代数とその周辺

檜山正幸 (HIYAMA Masayuki)
Thu Jun 02 2005:start
Sat Jun 04 2005:partial

/* TBD */

目次

1. はじめに

「キマイラ飼育 記」のここ(*注1)でも予告したことだし、Kleene代数(*注2)とそれに関 連するいくつかの話題を解説する。

注1

僕の日記エントリーがGoogleの検索でトップになるという現象は一時的なも のだった。願わくば、この記事がいずれトップに来ますように(笑)。

注2

「クリーネ」とカタカナ書きすることが多いけど、守屋本p.161の「TEA TIME」 によると、「クリーン」のほうが原音に近いらしい。どっちのカタカナ表記を採 用するか決めかねているので、この記事では"Kleene"を使う。

参考文献は次の2つ:

これらを、[守屋]、[木下]として引用する。が、この2つだけからネタを採っ ているわけではない。

なお、 「キマイラ飼育記」の 2005-05-26から2005-05-30にかけて書いた日記エントリーの内容もこの記事に 含まれる。日記のほうが説明が簡潔だから、むしろこの記事を読む前に次に挙 げる日記エントリー群を(この順で)読んでおいたほうが理解しやすいかも知 れない。(本記事のほうが例は豊富なのだが、説明は抽象的である。)

  1. データ構造の基本としてのコレクション
  2. 演算「・」と定数「I」をオーバーロード定義する
  3. Power Liftingって、重量上げか?
  4. Kleene代数と正規表現
  5. バッグ正規表現の事例
  6. だから何なの?

Kleene代数に関する手短な紹介は、記事「『正 規(regular)』とは何なんだ 2 正規構造」の第5節にもある。

2. 半環とその例

集合R上に2項演算+、2項演算・、特定のメンバー0、 特定のメンバー1があって(*注3)、次の法則が成立するとき、(R; +, ・, 0, 1)を‘半環’(semiring)(*注4)と呼ぶ。(以下、x, yなどの変数はRのメン バーを表すとする。)

  1. (x + y) + z = x + (y + z)
  2. x + 0 = 0 + x = 0
  3. x + y = y + x
  4. (x・y)・z = x・(y・z)
  5. x・1 = 1・x = x
  6. x・(y + z) = x・y + x・z
  7. (x + y)・z = x・z + y・z
注3

記号「0」は(その他の記号も)、単なる定数記号で「O」とか「θ」とか 「zero」とか書いても何でもよい。このへんのことに付いては、 記事「『形式的』とは何だろう」を参照。

注4

半環をリグ(rig)と呼ぶこともある。環(ring)から、引き算またはマイナ スの概念を抜いたものだから "ring without negative" → "ring without n" →"ringからnを抜いてrig"、というわけだ。が、こんなダジャレは僕は嫌い。 それに、発音したときに「リング」と「リグ」では紛れる恐れがある。

半環のいちばん典型的な例は、0を含む自然数の集合N= {0, 1, 2, ...} に普通の足し算と掛け算を併せて考えたものだ。上に列挙した法則は、算数の 計算で無意識にでも仮定しているものである。法則1から法則3は、Rが演算+に 関して可換モノイドであること、同様に法則4と法則5は、Rが演算・に関して (必ずしも可換とは限らない)モノイドであることを述べている。演算・が可 換(x・y = y・x)のときは、Rは‘可換半環’であるという。

自然数以外の例を出そう。

・ 区間のmax-times代数

0以上1以下の実数の集合(区間[0, 1])を考える。足し算はmax(x, y)、掛け 算としては普通の実数の掛け算を考える。([0, 1]; max, ・, 0, 1)は可換半環に なる。

x, y∈[0, 1]なら、max(x, y)とx・yが再び[0, 1]に入るのは明らかだし、 2項演算max、・により、それぞれ0と1を単位(中立)元とする可換モノイドになる のもすぐに確認できる。分配律にあたる x・max(y, z) = max(x・y, x・z) は、 y ≦ z ならば x・y ≦ x・z のことだから、これも明らかだろう。

・ max-plus代数

すべての実数の集合(数直線)Rに負の無限大-∞を加えた集合を考える。 ただし、足し算を -∞ + x = x + -∞ = -∞ として拡張定義しておく。この R∪{-∞}の上に半環の構造を定義する。以下の記述は混乱しがちなので、 十分に注意。

半環の足し算はmax(x, y)、半環掛け算はx + yで定義する。すると、(R ∪{-∞}; max, +, -∞, 0)は可換半環になる。0は掛け算の単位元(中立元) なので、この半環の1は0である。この記述に混乱したら、 記事「『形式的』とは何だろう」を読んで、形 式的な記号とそれが指すモデルの区別に慣れてください。

・ 集合代数

Xを任意の集合として、Xのベキ集合をPow(X)とする。足し算はx∪y、掛け算 としてはx∩yを考える。(Pow(X); ∪, ∩, 0, X)は可換半環になる。ここで、 0は空集合、XはPow(X)のメンバーとしてのX自体(全体集合)である。

・ ブール代数

上の集合代数のXを{0}にすると、Pow(X) = {{}, {0}}となり、ブール代数と みなせる。[0, 1]区間のmax-times代数を{0, 1}に制限してもブール代数が得 られる。もちろん、より直接的に、真偽値{true, false}に論理的or、andの演 算を考えても同じことだ。

・ 部分半環

(R; +, ・, 0, 1)が半環のとき、Rの部分集合Sが次の条件を満たすとする。

  1. x, y∈S ならば、(x + y)∈R。
  2. x, y∈S ならば、x・y∈R。
  3. 0∈R
  4. 1∈R
このとき、(S; +, ・, 0, 1)を(R; +, ・, 0, 1)の部分半環と呼ぶ。

可換半環の部分半環は必ず可換である。非可換半環の部分半環は非可換のと きも可換のときもある。ブール代数は、集合代数の部分半環ともみなせるし、 区間のmax-times代数の部分半環ともみなせる。

・ 直積半環

RとSを台集合(underlying set)とする2つの半環があるとする。不正確では あるが(よく使われる習慣に従い)、演算や特殊元を同じ記号で表して、(R; +, ・, 0, 1)、(S; +, ・, 0, 1)を2つの半環だとする。集合R×S( 「タプルと直積」参照)上に次のようにして+と・ を定義する。

すると、(R×S; +, ・, (0, 0), (1, 1))は半環になる。例えば、Nを自 然数の半環として、N×Nはこの方法で半環になる。

・ 関数半環

(R; +, ・, 0, 1)を半環、Xを任意の集合として、f:X→Rを任意の関数(写像) とする。このようなfの全体をFunc(X, R)とし、集合Func(X, S)上に次の ようにして+と・を定義する。

すると、(Func(S); +, ・, c0, c1)は半環になる。ここで、c0, c1 は、それぞれ恒等的に0, 1の値をとる関数である。

Rをブール代数としたとき、Func(X, R)はPow(X)と1:1に対応する。 f:X→{true, false}に対して、{x∈X | f(x) = true}を対応させればよい。

・ 多項式半環

Rが可換半環であるとして、Xは単なる形式的な変数(不定元)だとして、 Rを係数とする変数Xの多項式の全体をR[X]とする。R[X]のメンバーは、a0, a1, ..., an をRのメンバーとして a0 + a1X + ... + anXn の形 に書ける。足し算と掛け算は普通通りに定義する。多変数の多項式も同様に定 義できる。

なお、Rが非可換のときは、常に a0 + a1X + ... + anXn の 形に表記することができない。

・ 加法を保つ写像の半環

(A; + , 0)を可換なモノイドとする。f:A→Aが、加法(+のこと)と0を保つ 写像だとする(つまり、fはモノイド射)。そのような写像の全体をRとする。 (f + g)(x) = f(x) + g(x)、(f・g)(x) = g(f(x))としてR上の加法と乗法を定 義する。(R; +, ・, c0, id)は半環になる。ここで、c0は恒等的に0の値 をとる写像、idはidentity mapである。

・ 行列半環

(R; +, ・, 0, 1)を半環としたとき、Rのメンバーを項目(成分)とする2×2 行列を考える。行列の足し算と掛け算は通常のとおりに定義する。 すると、2×2行列の全体は半環となる。一般的にn×n行列でも同じである。例 えば、RがNときは成分が自然数である行列となる。

Rが可換であっても、n=1を例外としてn×n行列の半環は可換ではない。

3. 関係、グラフ、行列

半環(実は、後でKleene代数であることも判明する)の重要な例である“関 係の半環”を導入する準備をする。集合Aに対して、A上の(2項)関係、Aを頂 点集合とする有向グラフ、A上のブール値係数行列が事実上同じ概念であることを、 この節で説明する。下に、A={1, 2, 3}の場合の図を載せておく。必要に応じ て図を確認してほしい。

FIG: 関係、グラフ、行列

A={1, 2, 3}, R={(1,1), (1, 3),(2,2)}

/* 図はまだ */

A上の(2項)‘関係’とは、直積A×Aの部分集合のことである。この定義に 違和感を感じる人もいるだろう。以下に事情を述べよう。

通常「関係」と呼ばれるモノの例として、「等しい」や「大小」を考えよう。 x, y∈Aだとして、x = y であるようなx, yの対(x, y)の全体は、直積A×Aの 部分集合である。すなわち {(x, y)∈A×A | x = y}という集合が考えられる。 この集合は図形的には対角線と思えるので、‘対角集合’とも呼ばれる。つま り、「等しい」という関係に対角集合が対応する。同様に、「大小」という関 係には、{(x, y)∈A×A | x ≦ y}という集合が対応する。

通常の感覚で“関係”(2項関係)と呼べるものには、必ず直積A×Aの部分集 合が対応する。よって、直積A×Aの部分集合を関係と呼んでしまうことにする。 対(x, y)が関係R(つまり R⊆A×A)に属するとき、「xとyのあいだに関係Rが 成立している」と解釈する。そして、(x, y)∈R を xRy とも書く。次のよう な書き方は、最初はギョッとするかも知れないが、xRy と (x, y)∈R が同じ 主張であると考えれば理解できるだろう(とはいっても、ひどい記法では あるが)。

Aを頂点集合とする‘有向グラフ’を考える。ただし、次の条件を満たすものに 話を限ろう。

  1. 任意のa, b∈Aに対して、aからbに向かう辺はたかだか1本である。(多重 辺を認めない。)
  2. aからaに向かう辺、つまりループを認める。ただし、上の条件から、多重 ループは認めない。

GがAを頂点集合とする有向グラフであるとき、Gの‘隣接行列’gが次の ように定義できる。

  1. gはA×Aのメンバー(a, b)に0か1(ブール値)を割り当てる関数である。 その値g(a, b)をga bとも書く。
  2. 頂点aからbに向かう辺があればgb a = 1、 そのような辺がなければgb a = 0とする。辺a→bに対して成分ga bで はなくてgb aを対応させるのは単なる習慣である(gb aはb行a列の成 分)。

集合Aに対して、A上の2項関係、Aを頂点集合とする有向グラフ(ただし、前 述した条件を満たす)、Aで添字付けられた正方行列の三者は、 次のように1:1対応する。

4. 関係の半環

集合Aを1つ固定する。A上の2項関係の全体をRel(A)とする。Rel(A)上に定義 される演算+と・を次のように定義する。

以下に述べるグラフを使った定義のほうが直感的かもしれない(図も参照)。 Aを頂点集合とする有向グラフの全体をGraph(A)とする。グラフに対する対応 する定義は次のようになる。

FIG: グラフの和と積

/* 図はまだ */

OとIは次のような関係/グラフだとする。

行列に関しては、演算+と・は行列の足し算と掛け算である。 ただし、1 + 1 = 1 として計算する。また、習慣により、G・Hに対応する行列 の積はh・gとなる(掛け算の順序が逆順になる)。

関係、グラフ、行列のいずれの場合でも、演算+と・、特殊なメンバーOとIに 関して半環となる。この事実を確認するには、行列の場合が一番簡単である (練習問題)。さらに、行列の積h・g がグラフG・Hの隣接行列を与えることは 次のようにしてわかる: h・g = k とする。kb aはΣ(hb x・gx a)で計算される。総和 (シグマ)は、xをA上で動かしてとる。hb x ・gx aが1となるxが1つ でもあれば総和は1となる。ここで、「hb x・gx a = 1」は、 「hb x = 1 かつ gx a = 1」のことだが、グラフとしては“aからxへ のGの辺”と“xからbへのHの辺”があることを意味する。 結局、「kb a = 1 ⇔ “aからxへのGの辺”と“xからbへのHの辺”がある」 だから、KはG・Hに他ならない。

5. 閉半環

閉半環はKleene代数の一歩手前ともいえる演算系(代数構造)である。 [木下]に紹介されている定義をわずかに変更した形で閉半環を導入しよう。

半環R(正確には(R; +, ・, 0, 1))がさらに次の性質を持つとき、Rを‘閉 半環’(closed semiring)と呼ぶ(*注5)

  1. a + a = a (ベキ等律)が成立する。
  2. 無限個のRのメンバーa0, a1, ... に対する和Σai が常に定義でき る。
注5

「閉半環」という呼び名はあまりいいとは思えない。が、既に使われている ようなので、この言葉を使うことにする。

「無限個の和」はもう少し正確に定義する必要があるだろう。まず、a≦bをa + b = bだと定義する。次が成立することは定義よりただちに確認できる。

  1. a ≦ a
  2. a ≦ b かつ b ≦ c ならば a ≦ c
  3. a ≦ b かつ b ≦ a ならば a = b
  4. 0 ≦ a

以上により、≦が順序であり、0が最小元であることがわかる。

無限列a0, a1, ... に対して、s0 = a0, s1 = s0 + a1, s2 = s1 + a2, ... のように定義すると、これは増大列となる。なぜなら、 sn+1 = sn + an+1 だから、sn + sn+1 = sn + sn + an+1 = sn + an+1 = sn+1 からsn ≦ sn+1 だからであ る。「無限個の和」は、この増大列の極限として定義すればいいので、次のよ うな条件を要求する。

  1. 任意の増大列 s0, s1, s2, ... の上限(最小の上界)が存在する。
  2. s0, s1, s2, ... の上限をsとすると、x・s0, x・s1, x・s2, ... の上限はx・s となる。
  3. s0, s1, s2, ... の上限をsとすると、s0・x, s1・x, s2・x, ... の上限はs・x となる。

無限個の和を増大列の上限で定義すれば、2番目と3番目の条件から無限分配 律が成立する。

既に挙げた例で、自然数の半環と多項式半環を除いて他は若干の条件付きで 閉半環になる。

  1. 区間のmax-times代数は閉半環である。
  2. max-plus代数は閉半環である。
  3. 集合代数は閉半環である。
  4. ブール代数は閉半環である。
  5. 閉半環の部分半環は閉半環とは限らない。が、任意の増大列の上限を 常に含むような部分半環は閉半環になる。
  6. 2つの閉半環の直積はまた閉半環である。
  7. Rが閉半環なら、Func(X, R)は閉半環になる。
  8. (A; +, 0)がベキ等な可換モノイドで、常に無限和が定義できるなら、無限和 (と0)を保つ写像f:A→Aの全体は閉半環となる。
  9. Rが閉半環なら、Rを係数とするn×n行列の全体も閉半環となる。

6. 閉半環の構成

この節では、モノイド、順序モノイドから閉半環を構成する方法を紹介する。

/* TBD */