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

  • 2
    $\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

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.