A1 Refereed original research article in a scientific journal
On the n-permutation Post Correspondence Problem
Authors: Mari Ernvall, Vesa Halava, Tero Harju
Publisher: Elsevier BV
Publication year: 2015
Journal: Theoretical Computer Science
Journal name in source: THEORETICAL COMPUTER SCIENCE
Journal acronym: THEOR COMPUT SCI
Volume: 601
Issue: 11
First page : 15
Last page: 20
Number of pages: 6
ISSN: 0304-3975
DOI: https://doi.org/10.1016/j.tcs.2015.07.021
We give new and simpler proof for the undecidability of the n-permutation Post Correspondence Problem that was originally proved by K. Ruohonen [10]. Our proof uses a recent result on deterministic semi-Thue systems according to which it is undecidable for a given deterministic semi-Thue system T and a word u whether or not there exists a nonempty cyclic derivation is u in u -> (+)(T) u. (C) 2015 Elsevier B.V. All rights reserved.