<p>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 <a href="https://www.irif.fr/~jep/PDF/ThemeVariations.pdf" rel="nofollow noreferrer">[1]</a> for instance).</p>

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

CC BY-SA 4.0
2018-06-09T18:29:57.823Z
Thanks for the reference, but I am afraid this paper does not answer the question, except in a very special case.
J.-E. Pin
CC BY-SA 4.0
2018-06-05T07:49:45.707Z
2018-06-05T10:29:15.550Z
2018-06-05T10:29:15.550Z
C.P.
<p>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.</p>

<p>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 <a href="https://cstheory.stackexchange.com/questions/40922/example-of-monoid-m-such-that-operatornameratm-not-subseteq-operatorna?rq=1">this thread</a> for lots of examples. One particular simple example for Kleene star would be <span class="math-container">$(1,1)^* \subseteq \mathbb N^2$</span>. This set is not recognizable in <span class="math-container">$\mathbb N^2$</span>.</p>

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

CC BY-SA 4.0
2020-04-18T18:10:24.777Z
2020-04-18T18:10:24.777Z
StefanH
<p>Let $Rec(\Sigma)$ be the class of languages over $\Sigma^*$ recognizable by finite monoids. </p>

<p>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?</p>

<automata-theory>
Closure of Recognizable Languages under Kleene Star: Algebraic Proof?
user49692
# Closure of Recognizable Languages under Kleene Star: Algebraic Proof?

(Asked by: username_0 on 2018-05-31)

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?

**Tags:** automata-theory


---

## 2 answers

### Answer by username_1 on 2018-06-05. Score: 4

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]](https://www.irif.fr/~jep/PDF/ThemeVariations.pdf) 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>

> **Comments:**
> **username_2**: Thanks for the reference, but I am afraid this paper does not answer the question, except in a very special case.  

---

### Answer by username_3 on 2020-04-18. Score: 3

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](https://cstheory.stackexchange.com/questions/40922/example-of-monoid-m-such-that-operatornameratm-not-subseteq-operatorna?rq=1) 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*.


---

