9
$\begingroup$

Let $A$ be a finite alphabet. For a given language $L \subseteq A^{\ast}$ the syntactic monoid $M(L)$ is a well-known notion in formal language theory. Furthermore, a monoid $M$ recognizes a language $L$ iff there exists a morphism $\varphi : A^{\ast} \to M$ such that $L = \varphi^{-1}(\varphi(L)))$.

Then we have the nice result:

A monoid $M$ recognizes $L \subseteq A^{\ast}$ if $M(L)$ is a homomorphic image of a submonoid of $M$ (writen as $M(L) \prec M$).

The above is usually states in the context of regular languages, and then the above monoids are all finite.

Now suppose we substitute $A^{\ast}$ with an arbitrary monoid $N$, and we say that a subset $L \subseteq N$ is recognized by $M$ if there exists a morphism $\varphi : N \to M$ such that $L = \varphi^{-1}(\varphi(L))$. Then we still have that if $M$ recognizes $L$, then $M(L) \prec M$ (see S. Eilenberg, Automata, Machines and Languages, Volume B), but does the converse hold?

In the proof for $A^{\ast}$ the converse is proven by exploiting the property that if $N = \varphi(M)$ for some morphism $\varphi : M \to N$ and $\psi : A^{\ast} \to N$ is also a morphism, then we can find $\rho : A^{\ast} \to M$ such that $\varphi(\rho(u)) = \psi(u)$ holds, simply by choosing some $\rho(x) \in \varphi^{-1}(\psi(x))$ for each $x \in A$ and extending this to a morphism from $A^{\ast}$ to $M$. But this does not work for arbitrary monoids $N$ so I expect the above converse to be false then. And if it is false, for what kind of monoid beside $A^{\ast}$ is it still true, and did those monoids have received any attention in the research literature?

$\endgroup$
2
  • $\begingroup$ End of first paragraph: wouldn't be L instead of A? $\endgroup$ Jun 6, 2018 at 21:36
  • $\begingroup$ @MateusdeOliveiraOliveira Yes, thank for noticing! $\endgroup$
    – StefanH
    Jun 7, 2018 at 9:06

1 Answer 1

5
$\begingroup$

Yes, these monoids have received attention in the research literature and actually lead to difficult questions.

Definition. A monoid $N$ is called projective if the following property holds: if $f:N \to R$ is a monoid morphism and $h:T \to R$ is a surjective morphism, then there exists a morphism $g:N \to T$ such that $f = h \circ g$.

You can find a long discussion on projective monoids in [1], right after Definition 4.1.33. It is shown in particular that every projective finite semigroup is a band (a semigroup in which every element is idempotent). But the converse is not true and it is actually an open problem to decide whether a finite semigroup is projective.

[1] J. Rhodes and B. Steinberg, The $q$-theory of finite semigroups. Springer Monographs in Mathematics. Springer, New York, 2009. xxii+666 pp. ISBN: 978-0-387-09780-0

$\endgroup$
1
  • $\begingroup$ Thanks for your answer! But is this property really necessary, I mean it is sufficient, but does the "division property" of the syntactic monoid really fails in general, and if so do you have an example (or counter-example that if the syntactic monoid divides another monoid, then the other monoid also recognizes the subset from which the syntactic monoid is built)? $\endgroup$
    – StefanH
    Jun 6, 2018 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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