Amalgams of inverse semigroups and reversible two-counter machines

• Type: Article in International Scientific Journal
• Date: 2013

Authors

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

Journal

Title: Journal of Pure and Applied Algebra

Vol. 217

Pages: 585-597

ISSN: 0022-4049

Publisher: Elsevier

Indexing

ISI Web of Knowledge - 5 Citations

Scopus - 7 Citations

Other information

Authenticus ID: 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.

Language: English

Type (Professor's evaluation): Scientific

No. of pages: 13