Amalgams of inverse semigroups and reversible two-counter machines. (Q2376520): Difference between revisions

For an amalgam \([S_1,S_2;U]\) of inverse semigroups is constructed a 2-counter machine, which is deterministic, reversible, alternating (tapes for testing) and does not have dispensable state changes (normalized machine); \(S_1,S_2\) encode tapes and \(U\) handles the control of the machine. The acceptance problem for normalized 2-counter machines is undecidable and this allows to prove that there exists an amalgam \([S_1,S_2;U,\omega_1,\omega_2]\) of inverse semigroups such that (i) \(S_1,S_2\) have finite \(\mathcal R\)-classes (thus the word problem is solvable); (ii) \(U\) is a free inverse semigroup with zero of finite rank; (iii) the membership problem of \(\omega_i(U)\) is decidable in \(S_i\), \(i=1,2\); (iv) \(\omega_1,\omega_2\) and their inverses are computable functions; (v) finiteness of a given \(\mathcal D\)-class of \(S_1*_US_2\) is undecidable. The result is in contrast with the earlier result that the word problem for amalgamated free products of finite inverse semigroups is decidable [see \textit{A. Cherubini, J. Meakin} and \textit{B. Piochi}, J. Algebra 285, No. 2, 706-725 (2005; Zbl 1069.20052)].