Given a list of pairs ((x1,y1),(x2,y2),…,(xn,yn)) of non-empty words x1,x2,…,xn,y1,y2,…,yn find a non-empty list of indices i1,i2,…,im so that the concatination of xi1.xi2….xim equals yi1.yi2….yim.
The word pairs (xi,yi) of a problem case can well be imagined as dominoes, where on one half xi and on the other half yi are written. There are n types of dominoes and any number of dominoes are available.
The correspondence problem can now be understood as follows: Is there a sequence of dominoes so that the words on the upper half of the dominoes (read from left to right) produce the same word as the words (read from left to right) from the lower half of the merged dominoes?
max. depth:
JavaScript implementation of the PCP algorithm below. In some cases, in particular with big instances and large values for depth, this might crash the site.
Example two illustrates how even for small instances the solution might only be found with a huge amount of indices.
The Algorithm, given a list of pairs (n pairs) and a limit k, finds a list of indices that are a solution to the PVP problem.
solutions = {}
(1)FOR i = 1...n:
IF xi = yi:
return (i)
IF length(xi) < length(yi):
IF yi begins with xi:
solutions = solutions + (i)
IF length(yi) < length(xi):
IF xi begins with yi:
solutions = solutions + (i)
(2)FOR i = 1...k:
new_solutions = {}
(2.1) FOR solution in solutions:
(2.2) FOR j = 1...n:
(2.2.1) IF adding pair j would not break the solution:
new_solutions = new_solutions + (solution, j)
(2.3) IF new_solutions = {}:
return {}
(2.4) FOR solution in new_solutions:
IF length of concatination of all xi equals length of concatination of all yi:
return solution
solutions = new_solutions
In step (1) a solutions list is created. Solutions are checked for validity in (2.4). There are k iterations (2). For each iteration each solution in the set of possible solutions (2.1) is checked if there can be added one of each of the possible pairs of (xj,yj) (2.2). A pair can be added if the concatination of all the x and y in the solution concatinated with xj and yj, like in (1), the bigger concatination begins with the smaller of both concatinations. If no new possible solutions are found the search can be aborted in (2.3).
Inpired by https://webdocs.cs.ualberta.ca/~games/PCP/thesis/pcp.pdf (Chapter 2.2 An example of solving PCP instances).