Amalgams of inverse semigroups and reversible two-counter machines

We show that the word problem for an amalgam [S 1, S 2;U, ω 1, ω 2] of inverse semigroups may be undecidable even if we assume S 1 and S 2 (and therefore U) to have finite R-classes and ω 1, ω 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ützenbergergraphs to sequences of computations in the machine. © 2012 Elsevier B.V