クリーネ代数

数学において、クリーネ代数（クリーネだいすう、 スティーブン・コール・クリーネにちなんで名付けられた）は、閉包演算子を備えた冪等な（したがって部分的に順序付けられた）半環である。^{[1]これは、}正規表現で知られている演算を一般化したものである。

クリーネ代数と関連構造の様々な非同値な定義が文献で与えられている。^[2]ここでは、現在最も一般的と思われる定義を与える。

クリーネ代数は、集合 Aと、2 つの二項演算+ : A × A → Aと · : A × A → A、および 1 つの関数^*  : A → A (それぞれa + b、ab 、 a ^*と表記) を組み合わせたもので、次の公理が満たされます。

• + と · の結合法則: A内のすべてのa、b、cについて、 a + ( b + c ) = ( a + b ) + cかつa ( bc ) = ( ab ) cです。
• + の交換法則: Aの任意のa、bに対してa + b = b + a
• 分配法則: Aのすべてのa、b、cについて、 a ( b + c ) = ( ab ) + ( ac ) かつ ( b + c ) a = ( ba ) + ( ca )
• + と · の単位元: Aには元 0 が存在し、 Aのすべてのaに対して、a + 0 = 0 + a = aが成り立ちます。A には元 1 が存在し、A のすべての a に対して、a 1 = 1 a = aが成り立ちます。
• 0 による消滅: A内のすべてのaについて、 a 0 = 0 a = 0 です。

上記の公理は半環を定義します。さらに以下が必要です。

• +はべき等です: Aのすべてのaに対してa + a = aです。

これで、a ≤ bがa + b = b のときのみ(または同等に、a ≤ b がAにa + x = bとなるx が存在するときのみ。いかなる定義でも、a ≤ b ≤ aであればa = bとなる) と設定することで、 A上の半順序≤ を定義することが可能になった。この順序で、演算^*に関する最後の 4 つの公理を定式化できる。

• Aの すべてのaについて、 1 + a ( a ^* ) ≤ a ^*です。
• Aのすべてのa について、1 + ( a ^* ) a ≤ a ^*。
• aとx がAに含まれ、ax ≤ xである場合、a ^* x ≤ x
• もしaとxがAに含まれ、 xa ≤ xならば、x ( a ^* ) ≤ x ^[3]

直感的には、 a + b をaとbの「和集合」または「最小上限」と考え、abをa ≤ bならばax ≤ bxであるという意味で単調な乗算と考えるべきです。スター演算子の背後にある考え方は、a ^* = 1 + a + aa + aaa + ... です。プログラミング言語理論の観点からは、 + を「選択」、 · を「順序付け」、 ^*を「反復」と解釈することもできます。

Σ を有限集合 (「アルファベット」) とし、A をΣ 上のすべての正規表現の集合とします。2 つの正規表現が同じ言語を記述する場合、それらは等しいとみなされます。この場合、 A はKleene 代数を形成します。実際、これは、正規表現間の任意の方程式が Kleene 代数の公理に従うという意味で 自由Kleene 代数であり、したがってすべての Kleene 代数で有効です。

再び、 Σ をアルファベットとします。A をΣ 上のすべての正規言語の集合（または Σ 上のすべての文脈自由言語の集合、または Σ 上のすべての再帰言語の集合、またはΣ 上のすべての言語の集合）とします。すると、Aの 2 つの要素の和集合（+ と表記）と連結（· と表記）は再びAに属し、Aの任意の要素に適用されたKleene スター演算も A に属します。0 が空集合で、1 が空文字列のみを含む集合であるKleene 代数Aが得られます。

M を単位元eを持つモノイドとし、A をMのすべての部分集合の集合とする。そのような 2 つの部分集合SとTについて、S + T をSとTの和集合とし、ST = { st  : s in S and t in T } と設定する。S ^*は、 Sによって生成されるMのサブモノイドとして定義され、 { e } ∪ S ∪ SS ∪ SSS ∪ ...と記述できる。すると、 A は、 0 が空集合で 1 が { e } であるクリーネ代数を形成する。任意の小さなカテゴリに対して、同様の構成を実行できる。

体上の単位代数の線型部分空間はクリーネ代数を形成します。線型部分空間VとW が与えられたとき、V + W を2 つの部分空間の和、 0 を自明な部分空間 {0} と定義します。V · W = span {v · w | v ∈ V, w ∈ W} を、それぞれVとWからのベクトルの積の線型範囲と定義します。1 = span {I} を、代数の単位の範囲と定義します。Vの閉包は、 Vのすべてのべき乗の直和です。

$${\displaystyle V^{*}=\bigoplus _{i=0}^{\infty }V^{i}}$$

Mが集合であり、A がM上のすべての二項関係の集合であるとします。 + を和集合、 · を合成集合、^{* を}反射推移閉包とすると、クリーネ代数が得られます。

および の演算を含むすべてのブール代数は、+ に対して を、· に対して を使用し、すべてのaに対してa ^* = 1を設定すると、クリーネ代数になります。 ${\displaystyle \lor}$${\displaystyle \land}$${\displaystyle \lor}$${\displaystyle \land}$

まったく異なるクリーネ代数を使用して、クリーネのアルゴリズムによって重み付き有向グラフのすべての2つの頂点について最短経路の長さを計算するフロイド-ワーシャル アルゴリズムを実装することができます。これは、決定性有限オートマトンのすべての2つの状態について正規表現を計算するものです。拡張された実数直線を使用して、a + b をaとbの最小値とし、ab をaとbの通常の和（+∞ と −∞ の合計は +∞ と定義されます）とします。a *^{は、非負の}aの場合は実数ゼロ、負のaの場合は −∞ と定義されます。これは、ゼロ要素 +∞ と 1 つの要素が実数ゼロであるクリーネ代数です。重み付き有向グラフは、各遷移に重みのラベルが付けられた決定性有限オートマトンと見なすことができます。任意の2つのグラフノード（オートマトン状態）について、クリーネのアルゴリズムから計算された正規表現は、この特定のクリーネ代数では、ノード間の最短経路長に評価されます。^[4]

ゼロは最小の要素です: A内のすべてのaに対して0 ≤ aです。

和a + b はaとbの最小の上限です。つまり、 a ≤ a + bかつb ≤ a + bであり、x がa ≤ xかつb ≤ x を満たすAの要素である場合、a + b ≤ xです。同様に、a ₁ + ... + a _{n は}要素a ₁、 ...、a _nの最小の上限です。

乗算と加算は単調である。a ≤ bならば、

• a + x ≤ b + x、
• ax ≤ bxであり、
• xa≤xbである。

A内のすべてのxについて。

スターオペレーションに関しては、

• 0 ^* = 1 かつ 1 ^* = 1、
• a ≤ b はa ^* ≤ b ^*を意味する（単調性）、
• 任意の自然数nに対してa ⁿ ≤ a ^*であり、a ^{n は}aのn倍として定義される。
• ( a ^* )( a ^* ) = a ^*、
• ( a ^* ) ^* = a ^*、
• 1 + a ( a ^* ) = a ^* = 1 + ( a ^* ) a、
• ax = xb は( a ^* ) x = x ( b ^* ) を意味します。
• (( ab ) ^* ) a = a (( ba ) ^* )、
• ( a + b ) ^* = a ^* ( b ( a ^* )) ^*であり、
• pq = 1 = qpはq ( a ^* ) p = ( qap ) ^*を意味します。^[5]

Aがクリーネ代数でnが自然数の場合、 Aに要素を持つすべてのn行n列の行列からなる集合 M _n ( A ) を考えることができます。行列の加算と乗算の通常の概念を使用して、 M _n ( A ) がクリーネ代数になる ように一意の^{*演算を定義できます。}

クリーネは正規表現を導入し、その代数法則のいくつかを与えた。^{[6] [7]} 彼はクリーネ代数を定義しなかったが、正規表現の同値性の決定手順を求めた。^{[8]レドコは、}等式公理の有限集合では正規言語の代数を特徴づけることができない ことを証明した。 ^[9] サロマはこの代数の完全な公理化を与えたが、問題のある推論規則に依存していた。^[10] 正規表現間のすべての等式の導出を可能にする公理の完全な集合を提供する問題は、ジョン・ホートン・コンウェイによって正規代数の名の下で集中的に研究されたが、^[11]彼の扱いの大部分は無限であった。1981年、コーゼンは正規言語の代数のための完全な無限等式演繹システムを与えた。^[12] 1994年に彼は上記の有限公理系を与えた。これは無条件等式と条件付き等式（a ≤ bをa + b = bの略記とみなす）を使用し、正規言語の代数に対して等式的に完全である。つまり、2つの正規表現aとbは、上記の公理からa = bが従う場合にのみ同じ言語を表す。^[13]

クリーネ代数は、閉半環の特殊なケースであり、準正則半環またはレーマン半環とも呼ばれ、すべての要素が少なくとも1つの準逆方程式a * = aa * + 1 = a * a + 1を満たす半環です。この準逆は必ずしも一意ではありません。^{[14] [15]}クリーネ代数では、a * は不動点方程式X = aX + 1およびX = Xa + 1の最小解です。^[15]

閉じた半環とクリーネ代数は、最短経路問題の一般化である代数的経路問題に現れる。^[15]

• アクション代数
• 代数構造
• クリーネスター
• 正規表現
• スターセミリング
• 評価代数

• コーゼン、デクスター。 「CS786 04年春 クリーン代数入門」。
• ピーター・ヘフナー (2009)。ハイブリッドシステムのための代数計算。BoD – オンデマンドブックス。pp. 10–13。ISBN 978-3-8391-2510-6。この本の序文では、上記の記事では説明されていない、過去 20 年間のクリーネ代数の分野での進歩について概説しています。