# Rational subsets of a monoid

In "Rational Set of Commutative Monoid", S. Eilenberg and M.P. Schützenberger define the class of rational subsets of a monoid $M$ as the least class $F$ of subsets of $M$ such that satisfy the following properties:

1. the empty set is in $F$;

2. Each single element set is in $F$;

3. If $X, Y$ are in $F$, then $X \cup Y$ is in $F$;

4. If $X, Y$ are in $F$, then $XY$ is in $F$;

5. If $X$ is in $F$, then $X^*$ is in $F$.

In 4. $XY = \{xy \mid x \in X \text{ and } y \in Y \}$, what is this product? concatenation product?

In the following link, there is a complete paper http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1969-3RationalSetsCommutativeMonoids.pdf

The product is the monoid product. A monoid is a set equipped with an operation (which we can call product) satisfying certain axioms. The classical monoid we use in formal languages is $\Sigma^*$ (for some alphabet $\Sigma$), in which case the monoid product is indeed concatenation. But this is not the only possibility: for example, every group is a monoid, since the monoid axioms are a subset of the group axioms.

• X, Y are monoids? May 7, 2015 at 14:57
• They are subsets of the monoid M. May 7, 2015 at 15:04
• For example, I consider the monid M = (N, +), where N is the set of natual number, and + is the "traditional" addiction. For X, Y $\subset$, XY = {x+y | x $\in$ X and y $\in$ Y }. Is it right? May 7, 2015 at 15:12
• That's exactly right. May 7, 2015 at 16:11
• ... and $X^*$ is the submonoid of $M$ generated by $X$. May 7, 2015 at 16:54

Yes, it's a lifting of the monoid product $$x, y ∈ M ↦ xy ∈ M$$ onto a product $$A, B ∈ 𝔓M ↦ AB ∈ 𝔓M,$$ that makes the power-set $$𝔓M$$ of $$M$$ into a monoid, and $$M$$, itself, a sub-monoid of $$𝔓M$$ via the inclusion $$η_M: m ∈ M ↦ \{m\} ∈ 𝔓M.$$ So, it is a way of extending the product operation from individuals to subsets.

The resulting algebra contains not just the monoid structure, but a sum operation $$A, B ∈ 𝔓M ↦ A + B = A ∪ B ∈ 𝔓M,$$ that is idempotent ($$A + A = A$$) and a zero element $$0 = ∅$$ that serves as the additive identity. It is a monoid this way, too, both idempotent and commutative ($$A + B = B + A$$) ... which is equivalent to the structure for an upper semi-lattice.

The sum operation is, of course, what encodes branching, both the non-deterministic variety and (ultimately) even the deterministic ("if then else") variety. The algebra contains much more structure than that, actually, since the sum operation extends to an infinitary sum $$Y ∈ 𝔓𝔓M ↦ ∑Y = ⋃Y$$ that satisfies infinitary distributivity $$P \left(∑Y\right) Q = ∑_{A ∈ Y}(P A Q)$$, for any $$Y ∈ 𝔓𝔓M$$.

The resulting algebra is known as a Quantale, with unit.

The quantales $$𝔓M$$, that arise as free extensions of monoids $$M$$ do not exhaust the list of quantales. An example of a non-free quantale would be that which has the commutativity relation on it $$AB = BA$$, which ties into your query. Another (more interesting) example of a non-free quantale consists of taking an already-existing quantale and freely extending it with addition of indeterminates $$\{b,d,p,q\}$$ that satisfy the relations $$bd = 1 = pq,\quad bq = 0 = pd,\quad db + qp = 1,$$ where the indeterminates are assumed to commute with the rest of the quantale that they have been added to. This proves to be sufficient, for instance, in algebraically representing solutions to fixed point relations (e.g. relations that encode context-free grammars); i.e. in providing us with an algebra for context-free expressions.

The operations $$η_M(m)$$ and $$μ_M(Y) = ∑Y$$ are exactly those that characterize a Monad, and the algebras (and associated categories) arising from them are called Eilenberg-Moore Algebras/Categories (there's also mention of this under the Monad link).

Other subset families, besides $$𝔓M$$ may also yield such algebras. The case in point, which is the topic of your query, are the rational subsets $$𝔑M$$ of a monoid $$M$$. The corresponding algebra, that arises from this, has $$∑$$ and distributivity with respect to it, for all subsets $$Y ∈ 𝔑𝔑M$$, is none other than the Kleene algebra associated with regular expressions. The infinite distributivity axiom can be fully and equivalently captured by the *-continuity identity $$u (1 + x + xx + xxx + ⋯) v = u x^* v.$$ Another, as-of-yet, lesser-known example are the context-free subsets $$ℭM$$ of a monoid $$M$$. The corresponding algebras are (now) known to be equivalently described as Kleene algebras that have $$μ$$-continuity: $$u (1 + f(0) + f(f(0)) + f(f(f(0))) + ⋯) v = u (μx·f(x)) v,$$ for all Kleene-algebraic expressions $$f(x)$$ in $$x$$. The term $$μx·f(x)$$ denotes the least fixed-point solution to $$x ≥ f(x)$$ which is how one algebraically encodes an EBNF grammar rule $$x → f(x)$$. As an example: the grammar $$L → 1,\quad L → L A,\quad A → u L v,\quad A → x,\quad L z,$$ where the final item denotes the top-level expression, would be represented as $$μℓ·(1 + ℓ (μa·(u ℓ v + x))) z,$$ which is a 1970's old-school "context-free expression" for the solution, that can now be more directly written as the context-free expression $$b (u p + x + q v)^* d z$$. (Edit: I had the order of $$a$$ and $$ℓ$$ backwards in the original edit because I changed the top-level expression in the example, in mid-stream, from $$A z$$ to $$L z$$, while writing it up, but forgot to finish editing the change.)

For the commutative case - something that Schützenberger et al. weren't aware of at the time - not only does the Kleene algebra admit the left quotient $$x \backslash A = \{ m ∈ M: x m ∈ A \},$$ as an analogue of a partial derivative operator $$∂A/∂x = x \backslash A$$, but, in the commutative case, it satisfies the Leibnitz rule $$\frac{∂(AB)}{∂x} = A \frac{∂B}{∂x} + \frac{∂A}{∂x} B.$$ In fact, it goes much further than that. The *-operator behaves like an exponential, since $$(A + B)^* = A^* B^*,\quad 0^* = 1$$ and - using the *-continuity property - you can show that it satisfies the analogue of the exponential rule with respect to the quotient operator $$\frac{∂(A^*)}{∂x} = \frac{∂A}{∂x} A^*.$$

In fact, you can go even further than that and show that Kleene-algebraic expressions satisfy the analogue of Taylor's Theorem: $$f(x + h) = f(x) + f'(x + h) h.$$

You can also establish identities, such as this $$A^* f(A^* B) = A^* f(B)$$, where $$f(x)$$ is any Kleene-algebraic expression in $$x$$. This is enough to give you a closed-form expression for $$μx·f(x)$$.

To find the least solution to the fixed-point inequality $$x ≥ f(x)$$, use Taylor's Theorem to write $$x ≥ f(x) = f(0) + f'(f(x)) x.$$ From this, it follows that $$x ≥ f'(f(x)) x$$, since "$$+$$" is the least upper bound operator. In turn, this establishes $$x ≥ f'(f(x))^* x$$ and, since $$x ≥ f(0)$$, that $$x ≥ f'(f(x))^* f(0)$$. Finally, all Kleene-algebraic operators $$a, b ↦ a + b$$, $$a, b ↦ ab$$ and $$a ↦ a^*$$ are order-preserving, therefore all Kleene-algebraic expressions $$f(x)$$ are order-preserving, as functions of $$x$$. Thus, $$f'(f(x))^* ≥ f'(f(0))^*$$, and one has $$x ≥ f'(f(0))^* f(0)$$, thus establishing $$f'(f(0))^* f(0)$$ as a lower bound to all solutions to $$x ≥ f(x)$$.

It so happens that this is not only a lower bound to all such solutions, but is - itself - a solution. Write $$a = f(0)$$ and $$b = f'(a)$$, for brevity. Using Taylor's Theorem, one can write $$f(b^* a) = a + f(b^* a) b^* a.$$ Using the property $$f(b^* a) b^* = f(a) b^*$$, and using the Kleene-algebraic identity $$x^* = 1 + x x^*$$, one can rewrite this as $$a + f(b^* a) b^* a = a + b b^* a = (1 + b b^*) a = b^* a.$$

Thus, for commutative Kleene algebras, one has $$μx·f(x) = f'(f(0))^* f(0)$$. This is enough to show that $$ℭM = 𝔑M$$, when $$M$$ is a commutative monoid - an algebraic form of Parikh's Theorem.

It bears to point out that this applies generally to commutative Kleene algebras and that the full power of *-continuity is not required for the proof, only the axioms that $$x ≥ a x → x ≥ a^* x$$, $$x ≥ x b → x ≥ x b^*$$ and $$x^* ≥ 1 + x x^*$$.

If you apply this to the previously-cited example $$μa·(x + u \left(μℓ·(1 + ℓ a)\right) v) z$$ then you'll get $$μℓ·(1 + ℓ a) = a^* (1 + ℓ 0) = a^*,\\ μa·(x + u a^* v) = (u (x + u 0^* v)^* v)^* (x + u 0^* v) = (u (x + u v)^* v)^* (x + u v),$$ and after using some Kleene-algebraic identities (e.g. $$(x y^*)^* = 1 + x (x + y)^*$$), along with commutativity: $$(u (x + u v)^* v)^* (x + u v) = (1 + u v (x + u v)^*) (x + u v).$$ Thus, for the top-level expression, we get: $$(1 + u v (x + u v)^*) (x + u v) z.$$

All commutative Kleene-algebraic expressions are star-height 1, and can be expressed as a sum of monomials of the form $$P(x) Q(x)^*$$, where $$P(x)$$ and $$Q(x)$$ are star-height 0. The terms $$P(x) Q(x)^*$$ are actually what the 1960's paper you cited called "linear", while the sums of such terms were called, by the paper, "semi-linear".

Another example where this would be applied is to the expression $$μx·(1 + u x v)$$. Setting $$f(x) = 1 + u x v$$, one gets $$f'(x) = u v$$, and from this: $$a = f(0) = 1$$, $$b = f'(a) = u v$$ and $$b^* a = (u v)^*$$, so that $$μx·(1 + u x v) = (u v)^*$$.

For the non-commutative case, you need to bring in the extra indeterminates, in which case you could write the least fixed-point solution as the following context-free expression: $$μx·(1 + u x v) = b (u p)^* (q v)^* d$$. That representation is, ultimately, an evolutionary descendant of the representations that come out of the Chomsky-Schützenberger Theorem which may, therefore, be considered as a non-commutative version of the Parikh Theorem.

• That’s impressive! Apr 12 at 1:46