On the n-permutation Post Correspondence Problem - UTU Tutkimustietojärjestelmä

A1 Vertaisarvioitu alkuperäisartikkeli tieteellisessä lehdessä

On the n-permutation Post Correspondence Problem

Tekijät: Mari Ernvall, Vesa Halava, Tero Harju

Kustantaja: Elsevier BV

Julkaisuvuosi: 2015

Lehti:: Theoretical Computer Science

Tietokannassa oleva lehden nimi: THEORETICAL COMPUTER SCIENCE

Lehden akronyymi: THEOR COMPUT SCI

Vuosikerta: 601

Numero: 11

Aloitussivu: 15

Lopetussivu: 20

Sivujen määrä: 6

ISSN: 0304-3975

DOI: https://doi.org/10.1016/j.tcs.2015.07.021

Tiivistelmä

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.