(Generalized) Post Correspondence Problem and semi-Thue systems

Details (Generalized) Post Correspondence Problem and semi-Thue systems (Generalized) Post Correspondence Problem and semi-Thue systems

2008-02-06

arxiv.org/abs/0802.0726v5

Computer Science

Discrete Mathematics

Lecture notes. 14 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

(Generalized) Post Correspondence Problem and semi-Thue systems does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with (Generalized) Post Correspondence Problem and semi-Thue systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and (Generalized) Post Correspondence Problem and semi-Thue systems will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-559545