Every finitely generated submonoid of a free monoid has a finite Malcev's presentation

AbstractThere exist finitely generated submonoids of a free monoid which are not finitely presented and have even not a finite cancellative presentation.If Σ∗ is the free monoid on the alphabet Σ and if ϱ⊂Σ∗×Σ∗, let m(ϱ) be the smallest congruence of Σ∗ containing ϱ such that the monoid Σ∗⧸m(ϱ) can be embedded in a group. If a monoid M is isomorphic to Σ∗⧸m(ϱ), then (Σ, ϱ) is said to be a Malcev's presentation of M.We shall prove here the following theorem: “Every finitely generated submonoid of a free monoid has a finite Malcev's presentation and such a presentation can be effectively found”.The necessary and sufficient conditions for embedding a semigroup in a group given by A.I. Malcev and a graph for determining the relators are used to prove this theorem