×

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)\).

MSC:

20M07 Varieties and pseudovarieties of semigroups
20M05 Free semigroups, generators and relations, word problems
20M18 Inverse semigroups
Full Text: DOI