• TUCS Publication Series
• How to Publish in TUCS Series
• Publication Search
• Publication Graph
• Publication Input
• Publication Input Guide
• JuFo Browser

On n-permutation Post Correspondence Problem

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

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.

Files:

Full publication in PDF-format

BibTeX entry:

@TECHREPORT{tHaHaHu13a,
  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