A1 Refereed original research article in a scientific journal

On the n-permutation Post Correspondence Problem




AuthorsMari Ernvall, Vesa Halava, Tero Harju

PublisherElsevier BV

Publication year2015

JournalTheoretical Computer Science

Journal name in sourceTHEORETICAL COMPUTER SCIENCE

Journal acronymTHEOR COMPUT SCI

Volume601

Issue11

First page 15

Last page20

Number of pages6

ISSN0304-3975

DOIhttps://doi.org/10.1016/j.tcs.2015.07.021


Abstract

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