Where academic tradition
meets the exciting future

On n-permutation Post Correspondence Problem

Vesa Halava, Tero Harju, Mari Huova, On n-permutation Post Correspondence Problem. TUCS Technical Reports 1084, TUCS, 2013.


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.


Full publication in PDF-format

BibTeX entry:

  title = {On n-permutation Post Correspondence Problem},
  author = {Halava, Vesa and Harju, Tero and Huova, Mari},
  number = {1084},
  series = {TUCS Technical Reports},
  publisher = {TUCS},
  year = {2013},
  keywords = {Permutation Post Correspondence Problem, semi-Thue system, word problem, deterministic, cyclic derivation},
  ISBN = {978-952-12-2921-3 },

Belongs to TUCS Research Unit(s): FUNDIM, Fundamentals of Computing and Discrete Mathematics

Edit publication