Irreducibility of Endomorphisms of Finitely Generated Free Semigroups

Abstract

We introduce and investigate the irreducibility of endomorphisms of finitely generated free semigroups, i.e., we investigate when an endomorphism $\phi :{\Sigma }^{+}\to {\Sigma }^{+}$, where $\Sigma$ is any alphabet, can be nontrivially expressed as a composition $\phi ={\psi }_2\circ {\psi }_1$ of endomorphisms ${\psi }_1,{\psi }_2:{\Sigma }^{+}\to {\Sigma }^{+}$. We, hence, study a notion of primality in the endomorphism monoid of the free semigroup -- a natural and fundamental concept in this algebraic structure. We establish that irreducibility is a nontrivial property for the class of so-called rank-preserving endomorphisms, and we provide a characteristic condition separating the reducible and irreducible endomorphisms. We also characterise when an endomorphism is a factor of another endomorphism, analyse the non-uniqueness of factorisations of a rank-preserving endomorphism into its irreducible components, and investigate the use of incidence matrices to give insights into the (ir-)reducibility of rank-preserving endomorphisms.