World's most popular travel blog for travel bloggers.

# Rational subsets of a monoid

, ,
Problem Detail:

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

###### Answered By : Yuval Filmus

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.