Talk:Kleene algebra
|
|
Is it really true that there are two different notions of Kleene algebra? I know only the one that generalizes regular expressions with operations +, ·, * and constants 0 and 1. I guess it can be seen as a generalized boolean algebra, because it's almost a boolean ring. What other notion is there? AxelBoldt 04:56 Dec 10, 2002 (UTC)
After creating this disambiguation page I began to suspect that I was wrong, and that means so was Dexter Kozen, who is considered by many to be the foremost authority on Kleene algebras. Some months ago I posted a query on Kleene algebras to sci.math.research . Someone replied by telling me to ask Dexter Kozen, whom I had never heard of, and I sent him an email. After a brief exchange it began to look as if what he meant be "Kleene algebra" was entirely different from what I meant, and I quoted him a definition, found in Natural Dualities for the Working Algebraist, which I fell short of giving completely on the disambiguation page. He replied that that was a completely different thing from what he understood Kleene algebras to be, so apparently there were two different things with the same name. After creating the disambiguation page, I looked at some definitions of "Kleene algebra" on the web, and some of them that mention the "Kleene star" do look a lot like definitions of Boolean rings. They didn't say that the Kleene star is an involution, but if someone confirms that it is I will be even more inclined to suspect that Kozen got that wrong. -- Mike Hardy
I'll write about the thing I know as a Kleene algebra shortly; then we should be able to compare more cleanly with other proposed concepts. I suspect the two approaches are equivalent, similar to the two approaches to boolean algebras (as boolean rings or as special lattices). AxelBoldt 00:37 Dec 13, 2002 (UTC)
I just found that there are indeed two different but closely related definitions of Kleene algebra around: check the third page of http://web.comlab.ox.ac.uk/oucl/work/jeremy.gibbons/wg21/meeting56/desharnais.pdf. He explicitly refers to Kozen's definition. AxelBoldt 04:18 Dec 14, 2002 (UTC)
I have now gotten a confirmation of this point from an Infallible source, so it's probably correct: "Kleene algebra" can mean either of two things. -- Mike Hardy
- Ok, do you want to write about the second notion? AxelBoldt 03:06 Dec 24, 2002 (UTC)
BTW, since the multiplication is not commutative, I wonder if you need two distributive laws -- left and right? -- Mike Hardy
- Yup, thanks for the catch. AxelBoldt 03:06 Dec 24, 2002 (UTC)
I think I'll write something on the lattice-theory concept of Kleene algebra within a couple of weeks. -- Mike Hardy