Amalgams of inverse semigroups and reversible two-counter machines

• Tipo: Artigo em Revista Científica Internacional
• Data: 2013

Autores

Emanuele Rodaro (Autor) FCUP; Pedro V. Silva (Autor) FCUP

Revista

Título: Journal of Pure and Applied Algebra

Vol. 217

Páginas: 585-597

ISSN: 0022-4049

Editora: Elsevier

Indexação

ISI Web of Knowledge - 5 Citações

Scopus - 7 Citações

Outras Informações

ID Authenticus: P-002-002

DOI: 10.1016/j.jpaa.2012.08.012

Abstract (EN): We show that the word problem for an amalgam [S-1, S-2; U, omega(1), omega(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 omega(1), omega(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 Schutzenberger graphs to sequences of computations in the machine.

Idioma: Inglês

Tipo (Avaliação Docente): Científica

Nº de páginas: 13