克莱尼代数

在文献中给出了 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 代数的公理解决了这个问题。