On the n-permutation Post Correspondence Problem




Mari Ernvall, Vesa Halava, Tero Harju

PublisherElsevier BV

2015

Theoretical Computer Science

THEORETICAL COMPUTER SCIENCE

THEOR COMPUT SCI

601

11

15

20

6

0304-3975

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




Last updated on 2024-26-11 at 21:30