New proof for the undecidability of the circular PCP



: Vesa Halava, Tero Harju

Publisher: SPRINGER

: 2013

: Acta Informatica

: ACTA INFORMATICA

: ACTA INFORM

: 5-6

: 50

: 5-6

: 331

: 341

: 11

: 0001-5903

: 1432-0525

DOI: https://doi.org/10.1007/s00236-013-0183-5

: http://link.springer.com/journal/236/50/5/page/1


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.



Last updated on 2024-26-11 at 12:24