A1 Refereed original research article in a scientific journal
New proof for the undecidability of the circular PCP
Authors: Vesa Halava, Tero Harju
Publisher: SPRINGER
Publication year: 2013
Journal: Acta Informatica
Journal name in source: ACTA INFORMATICA
Journal acronym: ACTA INFORM
Number in series: 5-6
Volume: 50
Issue: 5-6
First page : 331
Last page: 341
Number of pages: 11
ISSN: 0001-5903
eISSN: 1432-0525
DOI: https://doi.org/10.1007/s00236-013-0183-5
Web address : http://link.springer.com/journal/236/50/5/page/1
Abstract
We give simpler proof for the undecidability of the circular Post Correspondence Problem that was originally proved undecidable by Ruohonen (Acta Informatica 19:357-367, 1983). The key feature of our proof is the undecidability of the word problem of special semi-Thue systems where derivations are deterministic and reversible for words containing a single occurrence of a letter from a given set.
We give simpler proof for the undecidability of the circular Post Correspondence Problem that was originally proved undecidable by Ruohonen (Acta Informatica 19:357-367, 1983). The key feature of our proof is the undecidability of the word problem of special semi-Thue systems where derivations are deterministic and reversible for words containing a single occurrence of a letter from a given set.
UTU Research Portal