Some new results on Post correspondence problem and its modifications (Q2729239)

The authors of the paper study the Post Correspondence Problem (PCP) and its modification. The PCP offers many interesting questions related to undecidability that the authors consider. More specifically the authors consider the proof of Halava, Hirvensalo and De Wolf that a marked PCP is decidable for all alphabet sizes. Then, the authors study the generalized PCP and consider briefly the ideas behind the proof of Halave, Harju and Hirvensalo that the marked generalized PCP is decidable regardless of the size of the domain alphabet.