A solution of the word problem for free \(^*\)-regular semigroups (Q5928478): Difference between revisions

An involutory semigroup is a unary semigroup \((S,\cdot,^*)\) satisfying \(a^{**}=a\), \((ab)^*=b^*a^*\), for all \(a,b\) in \(S\). If in addition \(aa^*a=a\), for every \(a\in S\) then \(S\) is said to be \(^*\)-regular. Let \(X=\{x_1,x_2\dots\}\) be a countable infinite alphabet and \(X^*\) be its disjoint copy. The free semigroup \(F\) on \(Y=X\cup X^*\) equipped with the obvious involution \((a^{\varepsilon_1}_1\cdots a^{\varepsilon_m}_m)^*=a^{-\varepsilon_m}_m\cdots a^{-\varepsilon_1}_1\), where \(\varepsilon_1,\dots,\varepsilon_m\in\{-1,1\}\), \(a_1,\dots,a_m\in X\), \(a^1=a\), \(a^{-1}=a^*\), is a free involutory semigroup on \(X\). Consider the relation \(\to=\{(abb^*bc,abc)\mid a,c\in F^1,\;b\in F\}\). The main result of the paper is that the relation \(\to\) is locally confluent. Denote by \(\vec a\) the canonical form of \(a\in F\). The set \(C=\{\vec a\mid a\in F\}\) of all \(\to\)-canonical forms, with the multiplication \(\vec a\circ\vec b=\vec{ab}\) and the involution \(^*\) is the free \(^*\)-regular semigroup on \(X\).