(Join work with Pedro Silva) We show that the word problem for an amalgam [S1, S2; U, ω1, ω2] of i
(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.

Date and Venue

Start Date
Venue
Sala 0.04 - Dep. Matemática / FCUP

Speaker

Emanuele Rodaro
(CMUP)

Area

Semigroups, Automata and Languages