We show that the word problem for an amalgam [S 1, S 2;U, ω 1, ω 2] of inverse semigroups may be undecidable even if we assume S 1 and S 2 (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ützenbergergraphs to sequences of computations in the machine. © 2012 Elsevier B.V.

Amalgams of inverse semigroups and reversible two-counter machines

Rodaro E.;
2013

Abstract

We show that the word problem for an amalgam [S 1, S 2;U, ω 1, ω 2] of inverse semigroups may be undecidable even if we assume S 1 and S 2 (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ützenbergergraphs to sequences of computations in the machine. © 2012 Elsevier B.V.
File in questo prodotto:
File Dimensione Formato  
Amalgams of inverse semigroups and reversible two-counter machines.pdf

Accesso riservato

: Publisher’s version
Dimensione 589.06 kB
Formato Adobe PDF
589.06 kB Adobe PDF   Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: http://hdl.handle.net/11311/1141871
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 7
  • ???jsp.display-item.citation.isi??? 5
social impact