Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids.

To show that $Rec(\Sigma)$ is closed under Kleene star, one would usually refer to the equivalence of recognizable and regular languages and invoke Kleene's theorem. Can anyone think of a direct algebraic proof of this closure property on the level of monoids?


For a pointer on concatenation-like operations (including Kleene star) and their impact on the algebraic structure, you can look to Schützenberger products (see here [1] for instance).

[1] Pin, Jean-Éric. "Theme and variations on the concatenation product." International Conference on Algebraic Informatics. Springer, Berlin, Heidelberg, 2011, https://www.irif.fr/~jep/PDF/ThemeVariations.pdf

  • 3
    $\begingroup$ Thanks for the reference, but I am afraid this paper does not answer the question, except in a very special case. $\endgroup$ – J.-E. Pin Jun 9 '18 at 18:29

I am not quite sure what you mean by algebraic. But if you mean by just using the definition in terms of recognizing morphisms in such a manner that the proof would easily generalize to other monoids, then this would not be possible.

The reason is that recognizable languages in general are not closed under Kleene star. Or more specifically, in general we have rational sets that are not recognizable. See this thread for lots of examples. One particular simple example for Kleene star would be $(1,1)^* \subseteq \mathbb N^2$. This set is not recognizable in $\mathbb N^2$.

But, interestingly, the recognizable sets are closed under concatenation. You can proof this with Schützenberger products. A definition of this product could be found in S. Eilenberg, Automata, Languages and Machines, Volume B.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.