Talk:Kleene algebra
From Wikipedia, the free encyclopedia
 |
|||||||||||||||||||||||
| Mathematics rating: | Start Class | Mid Priority | Field: 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)
- There are numerous axiom sets that may be used to formulate a Kleene algebra. What they all have in common is the dioid structure for the additive and multiplicative operators. (A dioid is sometimes also known as an idempotent semiring). The "combinatorial" formulation, which cites a small set of identities or conditional identities such as x* = 1 + x x* and a + bx + xc <= x --> b* a c* <= x may be regarded as the simplest of the possibilities. The dioid, in turn, can be thought of either as an algebra with an addition and multiplication, or as a semi-lattice with a multiplication. Addition is just the semi-lattice operation.
- Other axiom sets may generally posit a "continuity" property on the star operator, namely that x* should be the least upper bound of all the powers of x. This property, when asserted in context (i.e., that b x* c should be the least upper bound of bc, bxc, bxxc, ..., for all powers of x) is called *-continuity.
- More generally, you can have different algebras depending on what you allow to have least upper bounds (e.g. rational subsets, countable subsets, general subsets, etc.), and what range distributivity is to apply over. When least upper bounds and distributivity are assumed for general subsets, the result is an algebra known as a quantale (or, more precisely, a quantale with a unit). This, along with dioids, are commonly studied in non-linear dynamics and quantum physics.
- The hierarchy of algebras, where different ranges of subsets are allowed to have least upper bounds, in many ways mimicks the Chomsky hierarchy and can, itself, be considered as a kind of algebraic rendition of the AFL concept of formal language theory. So, the fact that multiple definitions for Kleene algebras may exist is not, then, seen as a minus, but actually as a major bonus: namely, that of having embodied an algebraic rendition of a Chomsky-like hierarchy. One algebra of interest is that where least upper bounds and distributivity are assumed for regular (or "rational") subsets. That, in fact, is equivalent to a *-continuous Kleene algebra. Another, is where the least upper bounds and distributivity are assumed for context-free subsets. That algebra (what one might term an "algebraic dioid") is heretofore unnamed. But it would, for instance, provide the arena for stating a fixed point theorem or for formulating a theory of context-free expressions analogous to the theory of regular expressions. -- Mark, 22 January 2007
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
[edit] Free variables in definition
The beginning of the article defines a Kleene algebra as possibly: "A bounded distributive lattice with an involution satisfying De Morgan's laws, and the inequality x∧−x ≤ y∨−y. ..." What are x and y, here? A5 18:57, 26 March 2007 (UTC)
- They are uniformly quantified variables, as it is often the case in mathematics. Pierre de Lyon 12:16, 2 April 2007 (UTC)
