Abstract
We prove that the word problem for the free product with amalgamation
S *UT of monoids can be undecidable, even when S
and T are finitely presented monoids with word problems that are decidable
in linear time, the factorization problems for U in each of S and
T, as well as other problems, are decidable in polynomial time, and
U is a free finitely generated unitary submonoid of both S and
T. This is proved by showing that the equality problem for the
tensor product S ⊗UT is undecidable and using known
connections between tensor products and amalgams. We obtain similar
results for semigroups, and by passing to semigroup rings, we obtain
similar results for rings as well. The proof shows how to simulate an
arbitrary Turing machine as a communicating pair of two deterministic
pushdown automata and is of independent interest. A similar idea is
used in a paper by E. Bach to show undecidability of the tensor
equality problem for modules over commutative rings.