A1 Refereed original research article in a scientific journal

Word problem for deterministic and reversible semi-Thue systems




AuthorsHalava V., Harju T.

PublisherSpringer New York LLC

Publication year2014

JournalSemigroup Forum

Journal name in sourceSemigroup Forum

Volume88

Issue2

First page 468

Last page478

Number of pages11

ISSN0037-1912

DOIhttps://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.



Last updated on 2024-26-11 at 20:44