Post Correspondence Problem

Input

Alphabet \(A\).

Two tuples \(s\) and \(t\) of equal length containing strings over \(A\).

For bounded problem: \(k \in \mathbb{N}\).

Output

Decision version

True or False.

Non-decision version

Indices: \(\{0, 1, \ldots, |s| \}\).

Any tuple of indices \((i_0, i_1, \ldots, i_n)\) so that

\(\oplus_{j=0}^n \\, s[i_j] = \oplus_{j=0}^n \\, t[i_j]\)

where \(\oplus\) means concatenate and

\(s[i_j]\) means the element of \(s\) at index \(i_j\).

So, \(1001 \oplus 00\) is \(100100\).

If no such tuple of indices exists, return False.

Algorithm

For the bounded problem.

Exercise

Write a Python function called corresponds. It should take two lists of the same length containing strings over the same alphabet. It shouls also take a positive integer k. It should return any list (of length at most k) of indices of the two lists such that it solves the Post Correspondence Problem. If there is none, the function should return False.

import itertools as it

def correspond(s, t, k):
  # List of the indices of s and t.
  inds = list(range(len(s)))
  # Loop up to and including k.
  for i in range(1, k + 1):
    # Generate all products of length i.
    for w in it.product(inds, repeat=i):
      # Concatenate strings in s.
      x = ''.join(s[k] for k in w)
      # Concatenate strings in t.
      y = ''.join(t[k] for k in w)
      # Compare.
      if x == y:
        return w
  # If we get here, there is no tuple.
  return False