Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It only takes a minute to sign up.
Sign up to join this community
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
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.
