Word problem for deterministic and reversible semi-Thue systems

: Halava V., Harju T.

Publisher: Springer New York LLC

: 2014

: Semigroup Forum

: 88

: 2

: 468

: 478

: 11

: 0037-1912

DOI: https://doi.org/10.1007/s00233-013-9550-3(external)

: http://api.elsevier.com/content/abstract/scopus_id:84898014386(external)

We prove that the word problem for semi-Thue systems is undecidable for systems where the derivation is always deterministic and reversible for words containing a single occurrence of a letter from a given set. © 2013 Springer Science+Business Media New York.