Amalgams of inverse semigroups and reversible two-counter machines

Abstract

We show that the word problem for an amalgam $[S_1,S_2;U,{\omega }_1,{\omega }_2]$ of inverse semigroups may be undecidable even if we assume $S_1$ and $S_2$ (and therefore $U$) to have finite $\mathcal{R}$-classes and ${\omega }_1,{\omega }_2$ to be computable functions, interrupting a series of positive decidability results on the subject. This is achieved by encoding into an appropriate amalgam of inverse semigroups 2-counter machines with sufficient universality, and relating the nature of certain \sch graphs to sequences of computations in the machine.

Cited by in corpus (2)

• Maximal subgroups of amalgams of finite inverse semigroups
• On periodic points of free inverse monoid endomorphisms