Amalgams of inverse semigroups and reversible two-counter machines.

Free semigroups, generators and relations, word problems (20M05) Inverse semigroups (20M18) Semigroups in automata theory, linguistics, etc. (20M35) Formal languages and automata (68Q45)

Abstract: We show that the word problem for an amalgam

[S_{1}, S_{2}; U, o m e g a_{1}, o m e g a_{2}]

of inverse semigroups may be undecidable even if we assume

S_{1}

and

S_{2}

(and therefore

U

) to have finite

m a t h c a l R

-classes and

o m e g a_{1}, o m e g a_{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.

Review text

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)].

Recommendations

Cites work

Cited in

(7)

This page was built for publication: Amalgams of inverse semigroups and reversible two-counter machines.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2376520)