Cheap and Secure Web Hosting Provider : See Now

Rational subsets of a monoid

, , No Comments
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

Asked By : Michela
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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/42269

3200 people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback