The word problem in the variety of inverse semigroups with Abelian covers. (English) Zbl 0864.20032
Let \(\widehat{\mathcal A}\) be the variety of inverse semigroups with \(E\)-unitary covers over abelian groups. The authors prove that any variety of inverse semigroups containing \(\widehat{\mathcal A}\) has undecidable word problem.
First they take a Minsky algorithm \(M\) which calculates a partially recursive function with non-recursive domain \(X\). So, the configurations \((2^m,1,0)\) and \((1,0,0)\) of \(M\) are equivalent, if and only if \(m\) is in \(X\). Next, they associate, with a configuration \(c\), a word \(w(c)\) over a certain alphabet. They construct an inverse semigroup \(S(M)\) with a finite presentation associated with the Minsky algorithm \(M\) such that \((2^m,1,0)\) and \((1,0,0)\) are equivalent if and only if \(w(2^m,1,0)=w(1,0,0)\) in \(S(M)\).
First they take a Minsky algorithm \(M\) which calculates a partially recursive function with non-recursive domain \(X\). So, the configurations \((2^m,1,0)\) and \((1,0,0)\) of \(M\) are equivalent, if and only if \(m\) is in \(X\). Next, they associate, with a configuration \(c\), a word \(w(c)\) over a certain alphabet. They construct an inverse semigroup \(S(M)\) with a finite presentation associated with the Minsky algorithm \(M\) such that \((2^m,1,0)\) and \((1,0,0)\) are equivalent if and only if \(w(2^m,1,0)=w(1,0,0)\) in \(S(M)\).
Reviewer: Y.Kobayashi (Funabashi)
MSC:
20M07 | Varieties and pseudovarieties of semigroups |
20M05 | Free semigroups, generators and relations, word problems |
20M18 | Inverse semigroups |