Kleene代数
概要
Kleene代数（Kleene algebra）とは、加法が冪等な半環に単項演算 $a\mapsto a^{*}$ を加え、$1+aa^{*}\le a^{*}$ と、$b+ax\le x$ ならば $a^{*}b\le x$ という形の等式と等式の含意を課した代数構造である。$a^{*}b$ は $x\mapsto b+ax$ の最小の前不動点であり、言語の Kleene 閉包、2 項関係の反射推移閉包、非負の重みの最短経路などが例になる。ずらしの法則や星の分解は公理から導け、Kozen の完全性定理により、言語として正しい正規表現の等式はすべて公理から導ける。
正規表現 の記事の命題「正規表現の代数法則」は、言語の和・連接・Kleene 閉包が満たす等式を集めたものである。$\alpha^{*}\equiv\varepsilon+\alpha\alpha^{*}$ や $(\alpha+\beta)^{*}\equiv(\alpha^{*}\beta^{*})^{*}$ のような等式は、言語だけでなく、2 項関係の合成と反射推移閉包でも、最短経路を計算する $(\min,+)$ の演算でも成り立つ。Kleene 代数 は、これらに共通する代数構造であり、「星 $a^{*}$ は $x=1+ax$ の最小の解である」という性質を、等式と等式の含意だけで公理にしたものである。
Kleene は正規表現の等式の公理化を問題として提起し、Kozen は 1994 年に、以下の有限個の等式と等式の含意から、言語として正しい正規表現の等式がすべて導けることを証明した（Koz94 Theorem 19、p. 26）。この記事では Kozen による定義を述べ、星の基本法則を公理から証明し、多くの例を一度に与える構成を示す。完全性定理そのものは言明と所在にとどめる。
定義
集合 $K$ と二項演算 $+,\cdot$、単項演算 $a\mapsto a^{*}$、元 $0,1\in K$ の組 $(K,+,\cdot,{}^{*},0,1)$ が Kleene 代数（Kleene algebra）であるとは、次を満たすことをいう（積 $a\cdot b$ は $ab$ と書く）。
- $(K,+,\cdot,0,1)$ は 半環 であり、加法は冪等（$a+a=a$）である。
- $a\le b:\iff a+b=b$ と定めた順序について、すべての $a,b,x\in K$ で次が成り立つ。
$$ 1+aa^{*}\le a^{*},\qquad 1+a^{*}a\le a^{*}, $$
$$ b+ax\le x\ \Longrightarrow\ a^{*}b\le x,\qquad b+xa\le x\ \Longrightarrow\ ba^{*}\le x. $$
この 4 つを順に (S1)–(S4) とよぶ。(S1)・(S2) は等式 $1+aa^{*}+a^{*}=a^{*}$ などと同じであり、(S3)・(S4) は等式の含意である。半環 の記事の命題「冪等な加法と順序」により、$\le$ は半順序で、$0$ は最小元、$a+b$ は $\{a,b\}$ の上限であり、和と積は $\le$ を保つ。
(S1) と分配法則から $b+a(a^{*}b)=(1+aa^{*})b\le a^{*}b$ なので、$x:=a^{*}b$ は $b+ax\le x$ を満たす。(S3) は、それが $b+ax\le x$ を満たす元の中で最小であることを言っている。すなわち $a^{*}b$ は単調な写像 $x\mapsto b+ax$ の最小の前不動点である（Koz94 §2、p. 6）。
文献には、Kleene 代数の定義として同値でないものがいくつかある（Koz94 p. 2）。この記事の定義は Koz94 §2（pp. 5–6）のものである。
例
例の多くは、次の構成から一度に得られる。
$(K,+,\cdot,0,1)$ を加法が冪等な半環とし、次を仮定する。
- （完備性）$K$ のすべての部分集合 $X$ が $\le$ についての上限 $\sup X$ をもつ。
- （無限分配法則）すべての $a\in K$ と部分集合 $X$ について $a\cdot\sup X=\sup\{ax\mid x\in X\}$、$(\sup X)\cdot a=\sup\{xa\mid x\in X\}$ である。
$a^{*}:=\sup\{a^n\mid n\ge0\}$（$a^0:=1$）とおくと、$(K,+,\cdot,{}^{*},0,1)$ は Kleene 代数である。
(S1)：無限分配法則により $aa^{*}=\sup\{a^{n+1}\mid n\ge0\}$ なので、$1+aa^{*}$ は $\{1\}\cup\{a^{n+1}\mid n\ge0\}=\{a^n\mid n\ge0\}$ の上限、すなわち $a^{*}$ に等しい。(S2) も同様である。
(S3)：$b+ax\le x$ とする。$n$ についての帰納法で $a^nb\le x$ を示す。$n=0$ では $b\le b+ax\le x$ である。$a^nb\le x$ なら、積が $\le$ を保つことから $a^{n+1}b=a(a^nb)\le ax\le b+ax\le x$ である。無限分配法則により $a^{*}b=\sup\{a^nb\mid n\ge0\}\le x$ となる。(S4) も同様である。$\square$
- 言語． アルファベット $\Sigma$ 上の言語の全体 $2^{\Sigma^{*}}$ は、和集合 $\cup$、連接、$\emptyset$、$\{\varepsilon\}$ で加法が冪等な半環になる。$\le$ は包含 $\subset$ で、上限は和集合であり、連接は任意個の和集合に分配する。thm-ka-complete の星は $L^{*}=\bigcup_{n\ge0}L^n$、すなわち 形式言語 の記事の Kleene 閉包である。
- 正規言語． 正規言語の全体 $\mathrm{Reg}_\Sigma$ は $\emptyset$、$\{\varepsilon\}$ を含み、和・連接・Kleene 閉包で閉じている（正規表現 の記事の定理「Kleene の定理」）。Kleene 代数の公理は全称の等式と等式の含意なので、演算で閉じた部分集合でも成り立ち、$\mathrm{Reg}_\Sigma$ は Kleene 代数である。ただし $\Sigma\ne\emptyset$ なら $\mathrm{Reg}_\Sigma$ は完備でない（$\Sigma=\emptyset$ なら $\mathrm{Reg}_\Sigma=2^{\Sigma^{*}}=\{\emptyset,\{\varepsilon\}\}$ である）。
- 2 項関係． 集合 $X$ 上の 2 項関係の全体は、和集合、合成 $R\cdot S:=\{(x,z)\mid\exists y\ (x,y)\in R,\ (y,z)\in S\}$、空関係、恒等関係で、1 と同じく thm-ka-complete の仮定を満たす（上限は和集合）。星 $R^{*}=\bigcup_{n\ge0}R^n$ は $R$ の反射推移閉包である。
- 最短経路． $[0,+\infty]$ に加法 $\min$、乗法 $+$（$a+\infty=\infty$）を入れたものは、半環 の記事の例「自然数・Boole 半環・トロピカル半環」のトロピカル半環の部分半環であり、$\le$ は通常の大小の逆である。$[0,+\infty]$ のすべての部分集合は下限をもち、$a+\inf X=\inf(a+X)$ なので thm-ka-complete が使え、星は $a^{*}=\inf\{na\mid n\ge0\}=0$ である。
- Boole 値． $\{0,1\}$ に論理和と論理積を入れたものでは、$0^{*}=1^{*}=1$ である。
4 で $0$ 以上の重みに限るのは本質的である（後の ex-ka-counterexamples）。重み付き有向グラフの隣接行列を考えると、行列の星の成分が 2 頂点間の最短経路の長さを与える（半環 の記事の定理「トロピカルな行列の冪と最短経路」と同じ考え方）。実際、Kleene 代数 $K$ 上の $n\times n$ 行列の全体は、行列の和と積で再び Kleene 代数になる（Koz94 Theorem 11、p. 14。星はブロックに分けた帰納的な式 (53) で与えられる。この記事では証明しない）。
基本的な性質
以下、$K$ は Kleene 代数とする。
- $a\le b$ なら $a^{*}\le b^{*}$ である。
- $a\in K$ に対し、$c\in K$ が「$1+ac\le c$」と「すべての $b,x$ で $b+ax\le x\Rightarrow cb\le x$」を満たすなら $c=a^{*}$ である。
1：$a\le b$ と (S1) から $1+ab^{*}\le1+bb^{*}\le b^{*}$ なので、(S3) を、その $b$ として $1$、その $x$ として $b^{*}$ をとって当てはめて $a^{*}=a^{*}\cdot1\le b^{*}$ を得る。
2：$c$ の第 2 の性質を $b:=1$、$x:=a^{*}$ に当てはめると、(S1) より $c\le a^{*}$ である。(S3) を $b:=1$、$x:=c$ に当てはめると、第 1 の性質より $a^{*}\le c$ である。$\square$
2 は、星が (S1) と (S3) だけで一意に決まることを言っている（Koz94 Lemma 1、p. 7）。とくに、ある半環に Kleene 代数の星を入れる方法はたかだか 1 通りである。
すべての $a,b\in K$ について次が成り立つ。
- $1+aa^{*}=a^{*}=1+a^{*}a$。
- $1\le a^{*}$、$a\le a^{*}$。
- $a^{*}a^{*}=a^{*}$、$(a^{*})^{*}=a^{*}$。
- $0^{*}=1$、$1^{*}=1$。
- $(a+b)^{*}=(a^{*}b^{*})^{*}$。
2：(S1) より $1\le1+aa^{*}\le a^{*}$ であり、$a=a\cdot1\le aa^{*}\le a^{*}$ である。
1：$\le$ は (S1) である。逆に $x:=1+aa^{*}$ とおくと、2 と (S1) から $1+ax=1+a+aaa^{*}\le1+aa^{*}+aa^{*}=x$（$a\le aa^{*}$ と $aa^{*}\le a^{*}$ を使った）なので、(S3) で $a^{*}\le x$ である。右側の等式も (S2)・(S4) で同様である。
3：$a^{*}+aa^{*}\le a^{*}$（(S1)）なので、(S3) を $b:=a^{*}$、$x:=a^{*}$ に当てはめて $a^{*}a^{*}\le a^{*}$ を得る。逆は $a^{*}=a^{*}\cdot1\le a^{*}a^{*}$（2）である。次に、2 と前半から $1+a^{*}a^{*}\le a^{*}$ なので、(S3) を $a^{*}$ の星に当てはめて $(a^{*})^{*}\le a^{*}$ を得る。逆は 2 を $a^{*}$ に当てはめればよい。
4：$1+0\cdot1=1\le1$ と (S3) から $0^{*}\le1$、$1+1\cdot1=1$ と (S3) から $1^{*}\le1$ である。逆は 2 による。
5：$a=a\cdot1\le a^{*}b^{*}$、$b\le a^{*}b^{*}$ なので $a+b\le a^{*}b^{*}$ であり、prop-ka-unique の 1 から $(a+b)^{*}\le(a^{*}b^{*})^{*}$ となる。逆に、単調性から $a^{*}b^{*}\le(a+b)^{*}(a+b)^{*}=(a+b)^{*}$（3）なので、$(a^{*}b^{*})^{*}\le((a+b)^{*})^{*}=(a+b)^{*}$ である。$\square$
5 は 正規表現 の記事の命題「正規表現の代数法則」の 4 の最後の等式であり、そこでは言語の上で確かめていた。ここでは Kleene 代数の公理だけから導いたので、関係や最短経路の例でも成り立つ。
ずらしと星の分解
- $ax=xb$ なら $a^{*}x=xb^{*}$ である。
- すべての $c,d$ について $(cd)^{*}c=c(dc)^{*}$ である。
1：まず $ax\le xb$ から $a^{*}x\le xb^{*}$ を導く。積の単調性から $axb^{*}\le xbb^{*}$ であり、(S1) と分配法則から $x+xbb^{*}=x(1+bb^{*})\le xb^{*}$ なので、
$$
x+a(xb^{*})\le x+xbb^{*}\le xb^{*}
$$
である。(S3) の含意を、その $b$ として $x$、その $x$ として $xb^{*}$ をとって当てはめると、$a^{*}x\le xb^{*}$ を得る。左右を入れ替えた議論（(S2) と (S4) を使う）で、$xb\le ax$ から $xb^{*}\le a^{*}x$ が出る。$ax=xb$ なら両方が使える。
2：1 を $a:=cd$、$x:=c$、$b:=dc$ に当てはめる。$(cd)c=c(dc)$ は積の結合律である。$\square$
2 は Koz94 Corollary 5（p. 9）で、1 は同 Proposition 4（pp. 8–9）である。言語で読むと、$(cd)^{*}c$ も $c(dc)^{*}$ も「$c$ と $d$ が $c$ で始まり $c$ で終わるように交互に並んだ列」を表している。
すべての $a,b\in K$ について $(a+b)^{*}=a^{*}(ba^{*})^{*}$ である。
$y:=a^{*}(ba^{*})^{*}$ とおく。
$(a+b)^{*}\le y$：(S3) の含意を、その $a$ として $a+b$、その $b$ として $1$、その $x$ として $y$ をとって当てはめるため、$1+(a+b)y\le y$ を示す。prop-ka-basic の 2 から $1=1\cdot1\le a^{*}(ba^{*})^{*}=y$ である。(S1) から $aa^{*}\le a^{*}$ なので $ay=aa^{*}(ba^{*})^{*}\le y$ である。また (S1) を $ba^{*}$ に当てはめて $(ba^{*})(ba^{*})^{*}\le(ba^{*})^{*}$、さらに $1\le a^{*}$ から $(ba^{*})^{*}\le a^{*}(ba^{*})^{*}$ なので、$by=(ba^{*})(ba^{*})^{*}\le y$ である。和をとって $1+(a+b)y\le y$ となる。
$y\le(a+b)^{*}$：$c:=(a+b)^{*}$ とおく。prop-ka-unique の 1 から $a^{*}\le c$ である。$b\le a+b\le c$ と prop-ka-basic の 3 から $ba^{*}\le cc=c$ なので、再び prop-ka-unique の 1 と prop-ka-basic の 3 から $(ba^{*})^{*}\le c^{*}=c$ である。よって $y\le cc=c$ である。$\square$
Koz94 Proposition 7（p. 9）と同じ主張である。この分解は、2 つの星が重なった式を 1 段ずつほどくのに使う。たとえば $a:=0$ とおくと $b^{*}=(b\cdot1)^{*}$ という自明な式になり、$b:=a$ とおくと $a^{*}=a^{*}(aa^{*})^{*}$ を得る。
完全性定理
$\Sigma$ 上の 正規表現 は、記号 $\emptyset,\varepsilon,+,{}^{*}$ と連接を Kleene 代数の $0,1,+,{}^{*},\cdot$ と読めば、Kleene 代数の項とみなせる。Kleene 代数 $K$ と写像 $I\colon\Sigma\to K$ に対し、正規表現 $\alpha$ の値 $I(\alpha)\in K$ が帰納的に定まる。$K=2^{\Sigma^{*}}$、$I(a)=\{a\}$ のときの値は、正規表現 の記事の定義「正規表現が表す言語」の $L(\alpha)$ にほかならない。
$\Sigma$ 上の正規表現 $\alpha,\beta$ について、次は同値である。
- $L(\alpha)=L(\beta)$。
- すべての Kleene 代数 $K$ とすべての $I\colon\Sigma\to K$ について $I(\alpha)=I(\beta)$。
2 ⇒ 1 は、ex-ka-examples の 1 で $K=2^{\Sigma^{*}}$、$I(a)=\{a\}$ とすればよい。1 ⇒ 2 が Kozen の定理であり、この記事では証明しない（Koz94 Theorem 19、p. 26。そこでは 2 を「$\alpha=\beta$ が Kleene 代数の公理から導ける」という形で述べており、等式論理の完全性により両者は同じである。同 p. 2）。証明は、正規表現を有限オートマトンの遷移行列で表し、部分集合構成による決定化と、最小の決定性有限オートマトンの一意性を、Kleene 代数の行列についての等式として代数的に書き直すことで行われる（Koz94 pp. 2–3 の概要）。この定理は、$\mathrm{Reg}_\Sigma$ が $\Sigma$ で生成される自由な Kleene 代数であることとも言い換えられる（Koz94 p. 2）。
完全性定理により、言語として正しい正規表現の等式は、どれも (S1)–(S4) と半環の公理から導ける。一方、含意を使わずに有限個の等式だけで正規表現の等式の全体を公理化することはできない。これは Redko によって示されている（Koz94 p. 2）。
反例：条件を外すと成り立たない
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| (S3)・(S4)（星の最小性） | $2^{\Sigma^{*}}$（$\Sigma\ne\emptyset$）で星をすべて $\Sigma^{*}$ とした構造 | prop-ka-basic の 4：$0^{*}=1$ |
| 完備性（thm-ka-complete の 1） | トロピカル半環 $\mathbb{R}\cup\{+\infty\}$（加法 $\min$、乗法 $+$） | (S1) を満たす星が存在すること |
1 行目：半環の公理は変わらず、$1+a\Sigma^{*}\subset\Sigma^{*}$、$1+\Sigma^{*}a\subset\Sigma^{*}$ なので (S1)・(S2) は成り立つ。しかし $\emptyset^{*}=\Sigma^{*}\ne\{\varepsilon\}$ である。(S3) は $a=\emptyset$、$b=x=\{\varepsilon\}$ で破れている（$b+ax=\{\varepsilon\}\subset x$ だが $a^{*}b=\Sigma^{*}\not\subset x$）。
2 行目：この半環の $\le$ は通常の大小 $\preceq$ の逆である。$a=-1$ に対し (S1) を満たす $c$ があったとすると、$1+ac\le c$ は $c\preceq\min\{0,-1+c\}$ を意味する。$c$ が実数なら $c\preceq c-1$ となって矛盾し、$c=+\infty$ なら $+\infty\preceq0$ となって矛盾する。$\{-n\mid n\ge0\}$ に下限がないので、$\sup\{a^n\}$ が存在しないことが原因である。重み付きグラフで言えば、負の長さの閉路があると最短経路の長さが定まらないことに当たる。$[0,+\infty]$ に制限すると ex-ka-examples の 4 のとおり Kleene 代数になる。
補足
- 公理系の由来． (S3)・(S4) の形の公理は Schröder と Dedekind にさかのぼり、Pratt が調べた（Koz94 p. 6）。(S3) を「$ax\le x\Rightarrow a^{*}x\le x$」に替えても、(S1) などのもとで同値である（同 Proposition 3、p. 8）。
- 正規表現の推論規則との違い． 正規表現 の記事の節「代数法則」の後で述べた Salomaa の推論規則は、「$\alpha$ が空語を含まない」という条件を含むので、文字に別の正規表現を代入すると成り立たなくなることがあり、言語以外の解釈では正しくない（Koz94 §1.2、pp. 4–5）。Kleene 代数の公理は全称の等式と等式の含意なので、どんな解釈でも正しく、代入も自由にできる。
関連項目
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
