Abstract:
Following the work done in $[\mathrm O]$ for groups, we describe, for a given semigroup $S$, which functions $l\colon S\to\mathbb{N}$ can be realized up to equivalence as length functions $g\mapsto|g|_{H}$ by embedding $S$ into a finitely generated semigroup $H$. We also, following the work done in $[\mathrm O_2]$ and $[\mathrm{OS}]$, provide a complete description of length functions of a given finitely generated semigroup with enumerable set of relations inside a finitely presented semigroup.
Keywords:Membership problem, word problem, embeddings of semigroups, length function, distortion.