Assignment 18 - Post's Correspondence Problem

1. Getting Started

   Please refer to this page for information on how to work on your assignment.

2. Outline

   Post's correspondence problem consists of two arrays of words, the first array and the second array. Both arrays have the same length, but the words in it can be of different length. A correspondence is a list of indices which tell how to arrange the elements of the arrays such that both give the same word. Examples can be found in the last lecture, note that the indexing of arrays starts in JavaScript with 0.

   (a)   Position         (0)     (1)     (2)     (3)      (4)
         First Array      abb     a       bab     baba     aba
         Second Array     bbab    aa      ab      aa       a
   
         Correspondence 1  1, 0, 0,  3,   0,  4
         First word        a abb abb baba abb aba
         Second word       aa bbab bbab aa bbab a
   
         Correspondence 2  1, 0, 4
         First word        a abb aba
         Second word       aa bbab a
                           (Thanks to Ryan Flynn for finding this one)
   
   (b)   Position        (0)     (1)     (2)     (3)      (4)
         First Array     a       aa      aba     aabb     abb
         Second Array    b       ba      bba     bbba     bba
   
         No correspondence exists
   

   Since this problem is unsolvable, it is impossible to write an algorithm which checks the existence of a correspondence. Nevertheless, one can check whether there is a correspondence of a given length. This should be implemented in this exercise.

3. What has to be done in detail

   The searchcorrespondence() function has to be implemented. It obtains three inputs: firstarray, secondarray and indexarray which are the parameters defining Post's correspondence problem and the array which will carry the correspondence. The length of this array is already given. The implementation should cover two aspects:

   • It should list all existing correspondences of the given length. For example, if indexarray is (0,0,0,0) and there are five columns, then the algorithm should check for all entries (a,b,c,d) with a,b,c,d in {0,1,2,3,4} whether these values of index array define a solution. The easiest way is to go in lexicographic order through all these possibilities.
   • Furthermore, the search is sometimes lengthy. Therefore it should be shortened in those cases where it is obvious that one cannot generate an entry. If in the case of the first example, all entries of the form (1,2,*,*) are impossible as the first row will start with "aplanacanal" and the second with "lanacanalpa" which cannot be matched to any matching correspondence.

   One can use the printcorrespondence(firstarray, secondarray, indexarray) function to print the existing solutions and also analyze this function in order to get an idea of how to test for correspondences. The function to be edited is the subsearch() function which is called from correspondencesearch(). Here it comes with a parameter k which says that indexarray[k] is now the variable which has to be set. The subsearch() function should call itself with all possible values inserted at indexarray[k]. It means that for any possible choice h the following should be done:

   • indexarray[k] should take the value h;
   • the function should be called with the value firstword + firstarray[h] instead of firstword, secondword + secondarray[h] instead of secondword, k + 1 instead of k.

   Furthermore, please optimize your solution. That is, do not make such a call if it can be eaisly seen that whatever will be done, it will not lead to a match. This optimization will speed up the processing of the search a lot.