·例子
·性质
·历史
·引用
在数学中，克莱尼代数（名称源自于美国数学家、逻辑学家斯蒂芬·科尔·克莱尼），又称kleene代数，是下列两个事物之一。
带有满足德·摩根定律和不等式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的子幺半群，它可以被描述为∪s∪ss∪sss∪...则a形成0为空集而1为的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。类似的，a1+...+an是元素a1,...,an的最小上界。
乘法和加法是单调性的:如果a≤b，则a+x≤b+x、ax≤bx和xa≤xb对于a中所有的x。
关于*运算，我们有0*=1和1*=1，*是单调性的(a≤b蕴涵a*≤b*)，而an≤a*对于所有自然数n。进一步的，(a*)(a*)=a*、(a*)*=a*和a≤b*当且仅当a*≤b*。
如果a是kleene代数而n是自然数，则你可以认为集合mn(a)由带有a中条目的所有n×n矩阵构成。使用普通的矩阵加法和乘法概念，你可以定义一个唯一的*-运算，所以mn(a)成为一个kleene代数。
历史kleene代数不是kleene定义的；他介入了正则表达式并寻求一个完备的公理集合来允许在正则表达式上的所有等式的推导。首先johnhortonconway在正则代数的名义下研究了这个问题。dexterkozen最先证明了kleene代数的公理解决了这个问题。
引用
dexterkozen:onkleenealgebrasandclosedsemirings.inrovan,editor,proc.math.found.comput.sci.,volume452oflecturenotesincomputerscience,pages26-47.springer,1990.onlineathttp://www.cs.cornell.edu/~kozen/papers/kacs.ps