GENERALIZED POST CORRESPONDENCE PROBLEM FOR MARKED MORPHISMS
Vesa Halava, Tero Harju, Mika Hirvensalo · International Journal of Algebra and Computation · 2000
We prove that the generalized Post Correspondence Problem (GPCP) is decidable for marked morphisms. This result gives as a corollary a shorter proof for the decidability of the binary PCP, proved in 1982 by Ehrenfeucht, Karhumäki and Rozenberg.