Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
435706 | Theoretical Computer Science | 2015 | 6 Pages |
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 u→T+u in T.
Keywords
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Mari Ernvall, Vesa Halava, Tero Harju,