Decidability and undecidability of marked PCP



: Halava V, Hirvensalo M, de Wolf R

: C. Meinel, S. Tison

: 1999

Lecture Notes in Computer Science

: STACS'99

STACS'99 - 16TH ANNUAL SYMPOSIUM ON THEORETICAL ASPECTS OF COMPUTER SCIENCE

: LECT NOTES COMPUT SC

: 1563

: 207

: 216

: 10

: 3-540-65691-X

: 0302-9743


We show that the marked version of the Post Correspondence Problem, where the words on a list are required to differ in the first letter, is decidable. On the other hand, PCP remains undecidable if we only require the words to differ in the first two letters. Thus we locate the decidability/undecidability-boundary between marked and a-marked PCP.



Last updated on 2025-13-10 at 13:43