D4 Julkaistu kehittämis- tai tutkimusraportti tai -selvitys
On n-permutation Post Correspondence Problem
Tekijät: Vesa Halava, Tero Harju, Mari Huova
Kustantaja: TUCS Technical Report 1084
Kustannuspaikka: Turku
Julkaisuvuosi: 2013
Verkko-osoite: http://tucs.fi/publications/view/?pub_id=tHaHaHu13a
Tiivistelmä
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.
Turun yliopiston Tutkimustietojärjestelmän portaali