Recently I have been studying Post's correspondence problem ($Pcp$), and I have stumbled upon a problem where I need to find a reduction from $Pcp$ to a modified version, $mPcp$. This modified version requires any matching sequence of "dominoes" $p_{i_1}, p_{i_2}, ..., p_{i_m}$ to start with the first "domino", $p_1$.
I am very well aware of the fact that there exists a match for an instance $I=\langle p_1, ..., p_n\rangle$ of $Pcp$ if and only if there exists a match for one of the instances $I_1, I_2, ..., I_n$ of $mPcp$ where $I_j=\langle p_j, p_{j+1}, ..., p_n, p_1, ..., p_{j-1}\rangle$ for $j=1, ..., n$. In other words, if and only if $I$ is a yes-instance for $Pcp$, there is a way to rotate the list of "dominoes" in a cyclic manner such that the starting piece in the found match for $Pcp$ is put in the first position.
However, it is not clear to me how this observation could lead to a mapping from an instance $I$ of $Pcp$ to the "correct" instance $I_j$ of $mPcp$ that can be carried out in a finite amount of steps for any $I$, thus serving as a suitable reduction.
Could anybody point me in the right direction? Thank you very much.
Put the *s before (or after) each symbol, not the words. So for d=(01101,001) add (0*1*1*0*1*,*0*0*1) but no (01101*,*001). If d is a starting domino add (*0*1*1*0*1*,*0*0*1), too.