Units of special Church-Rosser monoids (Q1821207): Difference between revisions

Let \(\Sigma\) be an alphabet, \(\Sigma^*\) the free monoid on \(\Sigma\) and \(R\subseteq \Sigma\). Let \(\sim\) denote the equivalence on \(\Sigma^*\) generated by a relation \(\to\) on \(\Sigma^*\) whereby \(w_ 1\to w_ 2\) iff there exists \(u,v\in \Sigma^*\) and \(r\in R\) such that \(w_ 1=urv\) and \(w_ 2=uv\). Then \(\sim\) is a congruence on \(\Sigma^*\), \(\Sigma^*/\sim\) is denoted by M(\(\Sigma\),R) and (\(\Sigma\),R) is called a special presentation of M(\(\Sigma\),R) which is called finite if both \(\Sigma\) and R are finite. A special presentation (\(\Sigma\),R) is said to have the Church-Rosser property provided for all \(x,y\in \Sigma^*\), whenever \(x\sim y\) then there exists \(z\in \Sigma^*\) such that \(x\to^*z\) and \(y\to^*z\) where \(\to^*\) is the reflexive, transitive closure of \(\to\). A monoid M which has a special presentation with the Church-Rosser property is called a special Church-Rosser monoid. This property is inherited by the submonoid of \(U_{\rho}(M)\) of right-invertible elements and U(M), the group of units of M. In this case U(M) is a free product of cyclic groups while \(U_{\rho}(M)\) is the free product of U(M) with a free monoid. In addition, finiteness of presentation and generating sets of the monoids involved is also preserved.