Problem Set 1
Assigned: Jan. 25
Due: Feb. 8
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.
D1 = "c/cca"
D2 = "ac/ba".
D3 = "bb/b".
D4 = "ac/cb".
Then the sequence D3, D2, D1, D4, D3 spells
out the string ``bbaccacbb'' 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 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 D1,D1 is a state since
the bottom "bbbb" is a prefix of the top "bbbbbb". The sequence D1,D2
is not a state because the top is "bbba" and the bottom is "bbbb" 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.
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.)
B. Show the state space that is generated if you use a depth-first search.
C. Show that if the dominos are tested in a different order, depth-first search
does not find the solution.
This state space is acylic, because the strings keep getting longer, but it
is not necessarily a tree. Give an example of a set of dominoes where the
state space is not a tree.
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.
A cleverer state space for this problem defines a "state" to be either the
part of bottom that goes past the top, or vice versa. For example, if you
have the dominoes
then the two strings [D1,D2]="abba/abbaab" and [D3]="ac/acab" can be considered
the same state, because in either case you have to "make up" a trailing "ab"
on the bottom, and any sequence that can be added after [D1,D2] to solve
the problem will work just as well when added after [D3].
Construct an example of a sequence of dominoes whose state space, defined this
way, has a cycle.