克莱尼代数,是数学名词,又称Kleene代数,是下列两个事物之一:带有满足德摩根定律和不等式xxyy的对合的有界分配格。所有布尔代数都是Kleene代数,但是多数Kleene代数不是布尔代数。克莱尼代数并非Kleene提出,但是他有着不可磨灭的贡献。
历史
Kleene代数不是Kleene定义的;他介入了正则表达式并寻求一个完备的公理集合来允许在正则表达式上的所有等式的推导。首先约翰何顿康威在正则代数的名义下研究了这个问题。DexterKozen最先证明了Kleene代数的公理解决了这个问题。
定义
在文献中给出了Kleene代数和相关结构的各种不等价的定义。总揽可见〔1〕。下面给出当代最常用的定义。
Kleene代数是带有分别写为ab、ab和a的,两个二元运算:AAA和:AAA,和一个函数:AA的集合A,所以满足下列公理。
和的结合律:a(bc)(ab)c和a(bc)(ab)c对于A中所有的a,b,c。
的交换律:abba对于A中所有的a,b。
分配律:a(bc)(ab)(ac)和(bc)a(ba)(ca)对于A中所有的a,b,c。
和的单位元:对于A中所有的a存在一个A中元素0使得:a00aa。对于A中所有的a存在一个A中元素1使得:a11aa。
a00a0对于A中所有的a。
上述公理定义了一个半环。我们进一步要求:
是等幂的:aaa对于A中所有的a。
现在可以定义在A上的偏序,通过设定ab当且仅当abb(或等价的:ab当且仅当A存在一个x使得axb)。通过这个次序我们可以公式化关于运算的最后两个公理:
1a(a)a对于A中所有的a。
1(a)aa对于A中所有的a。
如果a和x在A中使得axx,则axx。
如果a和x在A中使得xax,则x(a)...
(全文)