Encyclopedia > Talk:Kleene algebra

  Article Content

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Springs, New York

... families residing in the town. The population density is 225.9/km² (584.8/mi²). There are 3,878 housing units at an average density of 177.0/km² ...

 
 
 
This page was created in 31.6 ms