Talk:Kleene algebra

Untitled

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

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)

Split

This article obviously needs to be split as the two concepts both called Kleene algebra don't have anything in common except who discovered them. Even the bibliography is different, which is why they are both called Kleene without chance of confusion in most texts. Tijfo098 (talk) 18:49, 24 March 2011 (UTC)

Equivalence of the partial order criteria?

The article says:

a ≤ b if and only if a + b = b (or equivalently: a ≤ b if and only if there exists an x in A such that a + x = b)

I am unable to prove the equivalence of these two definitions. Can someone enlighten me?

- Taral (talk) 04:45, 11 August 2011 (UTC)

If a + b = b then there exists some x, namely b, such that a + x = b. Conversely if there exists some x such that a + x = b then, by using idempotentcy, a + b = a + (a + x) = a + x = b.

Inequality vs equality for * axioms?

I'm a bit confused.

The axioms have 1 + a(a*) ≤ a* for all a in A

But the page also says regexes form a free Kleene algebra. But for regexes, one has 1 + aa* = a*, not merely ≤

What am I missing? Given the rest of the Kleene algebra axioms, can I derive the equality? (I've fiddled with that a bit but so far haven't been able to derive such)

Or did I greatly misunderstand something?

Thanks. — Preceding unsigned comment added by Psy-Kosh (talk • contribs) 04:55, 31 January 2016 (UTC)

> But the page also says regexes form a free Kleene algebra. But for regexes, one has 1 + aa* = a*, not merely ≤

Well, logically, this is not a contradiction. Regexes form a Kleene algebra, and they might even have stronger properties. In the same spirit, the rationals form a ring, nothing wrong about that statement. 2001:6B0:2:2801:A510:7880:9229:762B (talk) 15:46, 15 August 2017 (UTC)

Since 1 + aa* = a* is later listed as one of the properties of Kleene Algebras, I agree it would make more sense to take this as an axiom rather than just 1 + aa* ≤ a*. (Even more so since an "algebraic theory" must be definable in terms of operations and equations only to deserve the name [but there is also the last 2 induction axioms may require ≤].) 90.231.119.119 (talk) 16:33, 13 September 2018 (UTC)

Somewhat hidden in section Kleene algebra#Definition, the article notes that "a≤b" can be defined as "a+b=b". Hence, all inequations can be expanded to equations. In particular, 1+aa*≤a* is equivalent to 1+a*+aa*=a*. — However, the theory is still not algebraic due to the conditional axioms "if ... then ...". As mentioned in section Kleene algebra#History, Redko has proved in 1964 that we can't do better. (Btw: I wonder if there is an English translation of his/her paper available?) - Jochen Burghardt (talk) 22:50, 13 September 2018 (UTC)