Amalgams of inverse semigroups and reversible two-counter machines

Sala 0.04 - Dep. Matemática / FCUP
Wednesday, 23 November, 2011 - 14:30

(Join work with Pedro Silva) We show that the word problem for an amalgam [S1, S2; U, ω1, ω2] of inverse semigroups may be undecidable even if we assume S1 and S2 (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ützenberger graphs to sequences of computations in the machine.

Speaker: 

Emanuele Rodaro (CMUP)
Error | CMUP

Error

The website encountered an unexpected error. Please try again later.