Suppose $M$ is a finitely generated monoid. A subset $X \subseteq M$ is said to be recognizable if there exists a homomorphism $\varphi : M \to K$ to some finite monoid $K$ satisfying $X = \varphi^{-1} \varphi(X)$.

It is well known that if $M$ is a group and $X$ is a subgroup of $M$, then $X$ is recognizable if and only if $X$ has finite index in $M$ (see e.g. J. Sakarovitch. Elements of Automata Theory, Cambridge University Press, 2009).

I was looking around for a similar kind of characterization of recognizable submonoids of monoids, but I could not find anything concrete. Now, naturally, a major issue right off the bat for generalizing the above result to monoids is that the concept of a finite index submonoid of a monoid is not really well defined. Furthermore, this question is already quite broad, and while any thoughts on this matter would be great, two more concrete and approachable questions would be:

  1. Is there a characterization of recognizable subgroups of f.g. monoids? It would especially interesting to know what role, if any, the maximal subgroup plays in such a characterization.
  2. Given a free submonoid $F$ of a f.g. monoid $M$, can anything be said about when $F$ is recognizable? Note that in the group case, by the earlier result a free subgroup is of course recognizable if and only if the larger group is virtually free. Also, if $M$ is a free monoid then $F$ is recognizable if and only if $F$ is rational, so in particular every f.g. (free) submonoid of a free monoid is recognizable.

Any input would be appreciated!


Your Answer

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

Browse other questions tagged or ask your own question.