克萊尼代數

克萊尼代數（名稱源自於美國數學家邏輯學家斯蒂芬·科爾·克萊尼）在數學中是下列兩個事物之一:

帶有滿足德·摩根定律和不等式 x∧−x ≤ y∨−y 的對合(補)運算的有界分配格。所以所有布爾代數都是 Kleene 代數，但是多數 Kleene 代數不是布爾代數。如同布爾代數有關於經典命題邏輯，Kleene代數有關於Kleene的三值邏輯。
推廣來源自正則表達式的運算的代數結構。本文餘下部分採用這種Kleene代數的概念。

定義

在文獻中給出了 Kleene 代數和相關結構的各種不等價的定義。總攬可見 [1]。下面給出當代最常用的定義。

Kleene 代數是帶有分別寫為 a + b、ab 和 a* 的，兩個二元運算 + : A × A → A 和 · : A × A → A，和一個函數 * : A → A 的集合 A，所以滿足下列公理。

+ 和 · 的結合律: a + (b + c) = (a + b) + c 和 a(bc) = (ab)c 對於 A 中所有的 a, b, c。
+ 的交換律: a + b = b + a 對於 A 中所有的 a, b。
分配律: a(b + c) = (ab) + (ac) 和 (b + c)a = (ba) + (ca) 對於 A 中所有的 a, b, c。
+ 和 · 的單位元: 對於 A 中所有的 a 存在一個 A 中元素 0 使得: a + 0 = 0 + a = a。對於 A 中所有的 a 存在一個 A 中元素 1 使得: a1 = 1a = a。
a0 = 0a = 0 對於 A 中所有的 a。

上述公理定義了一個半環。我們進一步要求:

+ 是等冪的: a + a = a 對於 A 中所有的 a。

現在可以定義在 A 上的偏序 ≤，通過設定 a ≤ b 當且僅當 a + b = b (或等價的: a ≤ b 當且僅當 A 存在一個 x 使得 a + x = b)。通過這個次序我們可以公式化關於運算 * 的最後兩個公理:

1 + a(a*) ≤ a* 對於 A 中所有的 a。
1 + (a*)a ≤ a* 對於 A 中所有的 a。
如果 a 和 x 在 A 中使得 ax ≤ x，則 a*x ≤ x。
如果 a 和 x 在 A 中使得 xa ≤ x，則 x(a*) ≤ x。

在直覺上，我們應當把 a + b 當作"並"或 a 和 b 的"最小上界"，和把 ab 當作某種單調性的乘法，在 a ≤ b 蘊涵 ax ≤ bx 的意義上。星號背後的想法是 a* = 1 + a + aa + aaa + ... 從編程理論的觀點，你還可以把 + 解釋所謂"選擇"，把 · 解釋為"順序"，把 * 解釋為"重複"。

例子

設 Σ 是有限集合("字母表")並設 A 是在 Σ 上所有正則表達式的集合。我們認為兩個正則表達式是相等的，如果它們描述同樣的語言。則 A 形成一個 Kleene 代數。事實上，這是自由 Kleene 代數，在正則表達式上的任何等式都從 Kleene 代數的公理得出，並且因此在所有 Kleene 代數中都是有效的意義上。

再次設 Σ 是字母表。設 A 是在 Σ 上所有正則語言的集合(或在 Σ 上所有上下文無關語言的集合；或在 Σ 上所有遞歸語言的集合；或在 Σ 上所有語言的集合)。則 A 的兩個元素的併集(寫為 +)和串接(寫為 ·)再次屬於 A，並且 Kleene星號運算也適用於 A 的任何元素。我們獲得了 0 為空集而 1 為只包含空字符串的集合的 Kleene 代數 A。

設 M 是帶有單位元 e 的幺半群，並設 A 是 M 的所有子集的集合。對於兩個這樣的子集 S 和 T，設 S + T 是 S 和 T 的併集並設 ST = {st : s ∈ S ∧ t ∈ T}。S* 被定義為 S 生成的 M 的子幺半群，它可以被描述為 {e} ∪ S ∪ SS ∪ SSS ∪ ... 則 A 形成 0 為空集而 1 為 {e} 的 Kleene 代數。對任何小範疇都可以進行類似的構造。

假設 M 是一個集合而 A 是在 M 上所有二元關係的集合。採用 + 為並，· 為複合，* 為自反傳遞凸包(hull)，我們就得到了 Kleene 代數。

帶有運算 ∨ 和 ∧ 的所有布爾代數成為 Kleene 代數，如果我們對 + 使用 ∨，對 ·使用 ∧，並對所有 a 設立 a* = 1。

在計算權重有向圖中的最短路徑的時候一個非常不同的 Kleene 代數是有用的: 設 A 是擴展的實數軸，採用 a + b 為 a 和 b 的最小者，而 ab 是 a 和 b 的普通和(帶有 +∞ 和 -∞ 的和並定義為 +∞)。a* 被定義對非負 a 為實數零對負 a 為 -∞。這是帶有零元素 +∞ 和一元素是實數零的 Kleene 代數。

性質

零是最小元素: 0 ≤ a 對於 A 中所有的 a。

a + b 的和是 a 和 b 的最小上界: 我們有 a ≤ a + b 和 b ≤ a + b 並且如果 x 是 A 的一個元素有着 a ≤ x 和 b ≤ x，則 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*)，而 aⁿ ≤ a* 對於所有自然數 n。進一步的，(a*)(a*) = a*、(a*)* = a* 和 a ≤ b* 當且僅當 a* ≤ b*。

如果 A 是 Kleene 代數而 n 是自然數，則你可以認為集合 M_n(A) 由帶有 A 中條目的所有 n×n 矩陣構成。使用普通的矩陣加法和乘法概念，你可以定義一個唯一的 *-運算，所以 M_n(A) 成為一個 Kleene 代數。

歷史

Kleene 代數不是 Kleene 定義的；他介入了正則表達式並尋求一個完備的公理集合來允許在正則表達式上的所有等式的推導。首先約翰·何頓·康威在正則代數的名義下研究了這個問題。Dexter Kozen 最先證明了 Kleene 代數的公理解決了這個問題。

參見

引用

Dexter Kozen: On Kleene algebras and closed semirings. In Rovan, editor, Proc. Math. Found. Comput. Sci., volume 452 of Lecture Notes in Computer Science, pages 26-47. Springer, 1990. Online at https://web.archive.org/web/20060923121313/http://www.cs.cornell.edu/~kozen/papers/kacs.ps