D4 Published development or research report or study
On n-permutation Post Correspondence Problem
Authors: Vesa Halava, Tero Harju, Mari Huova
Publisher: TUCS Technical Report 1084
Publishing place: Turku
Publication year: 2013
Web address : http://tucs.fi/publications/view/?pub_id=tHaHaHu13a
Abstract
We give new and simpler proof for the undecidability of the n-permutation Post
Correspondence Problem that was originally proved by K. Ruohonen (Acta
Informatica 19 (1983), 357 -- 367). Our proof uses a recent undecidability result on
deterministic semi-Thue systems that says that it is undecidable, for a given deterministic semi-Thue system T and a word u, whether or not there exists a nonempty cyclic
derivation u ->^+ u in T.
We give new and simpler proof for the undecidability of the n-permutation Post
Correspondence Problem that was originally proved by K. Ruohonen (Acta
Informatica 19 (1983), 357 -- 367). Our proof uses a recent undecidability result on
deterministic semi-Thue systems that says that it is undecidable, for a given deterministic semi-Thue system T and a word u, whether or not there exists a nonempty cyclic
derivation u ->^+ u in T.
UTU Research Portal