2008/02/06 by François Nicolas, Francois Nicolas, Nicolas, Francois · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Advanced Algebra and Logic #DNA and Biological Computing #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #cs.DM #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.0802.0726
Lecture notes. 14 pages
openalex publication_date 2008/02/06 · arxiv created 2008/11/12 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Let PCP(k) denote the Post Correspondence Problem for k input pairs of strings. Let ACCESSIBILITY(k) denote the the word problem for k-rule semi-Thue systems. In 1980, Claus showed that if ACCESSIBILITY(k) is undecidable then PCP(k + 4) is also undecidable. The aim of the paper is to present a clean, detailed proof of the statement. We proceed in two steps, using the Generalized Post Correspondence Problem as an auxiliary. First, we prove that if ACCESSIBILITY(k) is undecidable then GPCP(k + 2) is also undecidable. Then, we prove that if GPCP(k) is undecidable then PCP(k + 2) is also undecidable. (The latter result has also been shown by Harju and Karhumaki.) To date, the sharpest undecidability bounds for both PCP and GPCP have been deduced from Claus's result: since Matiyasevich and Senizergues showed that ACCESSIBILITY(3) is undecidable, GPCP(5) and PCP(7) are undecidable.