On the Complexity of the Bi-infinite Post Correspondence Problem

Olivier Finkel, Vesa Halava

In the bi-infinite Post Correspondence Problem ($\mathbb{Z}$PCP), it is asked whether the same bi-infinite word can be constructed correspondingly from a given finite set of pairs of words…