Amalgams of inverse semigroups and reversible two-counter machines
classification
🧮 math.GR
keywords
omegainversesemigroupsamalgammachinesachievedamalgamsappropriate
read the original 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.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.