Problem Set 1
Assigned: Jan. 19.
Due: Feb. 2.
POST CORRESPONDENCE PROBLEM is defined as follows:
You are given a collection of dominos. Each domino has a string of
characters on top and another string on the bottom. (Both strings
You can make as
many copies of the dominos as you need. The problem is to place the dominos
side by side so that the combination of the strings on the top is the
same as the combination of the strings on the bottom.
Suppose domino D1 has string ``bb" on top and string ``b''
on bottom; domino D2 has strings ``a'' and ``aab'' and domino D3 has
strings ``abbba'' and ``bb''. Then the ordering D2, D3, D2, D1 spells
out the string ``aabbbaabb'' both on the top and on the bottom.
The Post correspondence problem is, surpringly, only semi-decidable.
If there is an answer then, obviously, one can find it by exhaustive
search; however, there is no algorithm that always terminates and that
always answers correctly whether or not an instance of the problem
has a solution.
The problem can be characterized in terms of the following state space:
A. Suppose you solve the above example problem using a breadth-first
search. Show the state space that is generated. Assume that, where
there is a choice, the algorithm tests dominos in numerical
order (i.e. first D1, then D2 and so on.)
- A state is a sequence of dominos where either the top
string is a prefix of the bottom string or the bottom string is a
prefix of the top. For example, the sequence D2,D2 is a state since
the top "aa" is a prefix of the bottom "aabaab". The sequence D2,D1
is not a state because the top is "abb" and the bottom is "aabb" and
neither is a prefix of the other.
- An operator on D1 ... Dk is to add another domino at the end, if
that leads to a legitimate state.
- The start state is the empty sequence of dominos.
- The goal state is a non-empty sequence of dominos where the top
string and bottom string are equal.
B. What happens if you try to use depth-first search over the state space
in problem 1 to solve the example problem?
An alternative state space is to start at the end of the target sequence
and to build backward, toward the front.
As in Problem 1, show the state space generated using
breadth-first search to solve the example problem.
For the general problem, if there are N dominos,
what is the branching factor in the state space of problem 1?
Please do NOT give an answer that relates
to the characteristics of the particular example above.
Suppose that you modify the problem as follows:
The input contains a number M in addition to the dominos, and the
solution must contain at most M characters in the combined string.
(E.g. in the example problem, there are 8 characters in the solution
string "aabbaabb"). Let U be the length of the shortest string
on the top of the dominos, let V be the length of the shortest
string on the bottom of the dominos, and let K = max(U,V).
(E.g. in the example problem, U = 1, corresponding to string "b"
on D1; V = 1 corresponding to string "a" on D2; so K = 1.)
A. How could the description in problem 1 of a state be modified for
this new problem?
B. I claim that this modified state space has a depth of at most
M/K (rounding down). Give an argument justifying this claim.
Give an upper bound on the size of this state space in the general
case (again, without reference to the particular example.)
Construct a sample problem where the state space in Problem 1 is infinite
and the state space in problem 2 contains only the start space.
(Hint: There is an answer to this question using only two dominos
and where no string on the dominos is longer than two letters.)
The assignment is due at the beginning of class on the due date. I will
accept it up to one week late with a penalty of 1 point out of 10. It
may be submitted either in hard-copy (preferred) or by email to the TA
in plain-text, PDF, or Word.