Modified PCP many-one reduces to PCP

Introduce fresh symbols * and !. For a word $a_1\cdots a_k$, write $L(a_1\cdots a_k):=a_1\ast a_2\ast \cdots a_k\ast ,R(a_1\cdots a_k):=\ast a_1\ast a_2\ast \cdots \ast a_k\mathrm{.}$ Construct a PCP instance consisting of one special start tile, one shifted tile for each original domino, and one end tile: $(\ast L(x_1),R(y_1)),(L(x_i),R(y_i))(1\le i\le n),(!,\ast !)\mathrm{.}$ The extra leading * appears only on the special start tile, and ! appears only on the end tile.

If $1=i_1,i_2,\dots ,i_k$ is a modified-PCP match, choose the special start tile, then the ordinary shifted tiles for $i_2,\dots ,i_k$, and finally the end tile. The top concatenation is $\ast L(x_1)L(x_{i_2})\cdots L(x_{i_k})!,$ while the bottom concatenation is $R(y_1)R(y_{i_2})\cdots R(y_{i_k})\ast !\mathrm{.}$ Because the original match satisfies $x_1{x}_{i_2}\cdots x_{i_k}=y_1{y}_{i_2}\cdots y_{i_k}$, these two shifted strings agree symbol by symbol: the leading * on top supplies the one-symbol offset, every interior * matches the next boundary marker on the bottom, and the end tile matches the final extra *. Hence the transformed PCP instance has a match.

Conversely, let a PCP match be given for the transformed instance. The common concatenated word begins with *, and among the available top words only the special start tile begins with *, so the first chosen tile is the special start tile. Equality cannot be completed without an end tile. Consider the prefix ending at the first use of that tile. The fresh symbol ! occurs nowhere else, so its two first occurrences align and this prefix already has equal top and bottom concatenations. Delete the initial *, the terminal !, and all separator symbols * from this matched prefix. The remaining equality is $x_1{x}_{i_2}\cdots x_{i_k}=y_1{y}_{i_2}\cdots y_{i_k}\mathrm{.}$ Thus the recovered sequence begins with the original first domino and is a modified-PCP match. Later repetitions of the start or end tiles, if present in the original PCP match, are irrelevant because the first completed prefix has already supplied the required modified-PCP match.

Steps 2.1 and 2.2 prove the required equivalence, and the construction in step 1.1 is effective. Therefore modified PCP many-one reduces to PCP.