(Generalized) Post Correspondence Problem and semi-Thue systems
| dc.creator | Nicolas, Francois | |
| dc.date | 2008-02-06 | |
| dc.date | 2008-11-12 | |
| dc.date.accessioned | 2026-07-07T10:17:20Z | |
| dc.date.available | 2026-07-07T10:17:20Z | |
| dc.description | 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. | |
| dc.description | Lecture notes. 14 pages | |
| dc.identifier | https://arxiv.org/abs/0802.0726 | |
| dc.identifier | http://arxiv.org/abs/0802.0726 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/173816 | |
| dc.subject | Discrete Mathematics | |
| dc.title | (Generalized) Post Correspondence Problem and semi-Thue systems | |
| dc.type | text |