A1 Refereed original research article in a scientific journal
Word problem for deterministic and reversible semi-Thue systems
Authors: Halava V., Harju T.
Publisher: Springer New York LLC
Publication year: 2014
Journal: Semigroup Forum
Journal name in source: Semigroup Forum
Volume: 88
Issue: 2
First page : 468
Last page: 478
Number of pages: 11
ISSN: 0037-1912
DOI: https://doi.org/10.1007/s00233-013-9550-3
Web address : http://api.elsevier.com/content/abstract/scopus_id:84898014386
Abstract
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.
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.