## Problem Set 1

Assigned: Jan. 18.
Due: Feb. 1.

The 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 are non-empty.) 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.

Example: Suppose domino D1 has string ``bbb" on top and string ``bb'' on bottom; domino D2 has strings ``a'' and ``bb'' and domino D3 has strings ``bb'' and ``bba''. Then the ordering D3, D2, D1, D1 spells out the string ``bbabbbbbb'' 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.

### Problem 1

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.)

```empty --- D1 - bbb --- D1 - bbbbbb --- D1 - bbbbbbbbb --- D1 - bbbbbbbbbbbb
empty  |       bb           bbbb    |       bbbbbb     |       bbbbbbbb
|                            |                  |
|                            |                  |- D2 - bbbbbbbbba
|                            |                          bbbbbbbb
|                            |
|                            |- D2 - bbbbbba
|                                    bbbbbb
|
|- D3 - bb --- D2 - bba     --- D1 - bbabbb    --- D1 - bbabbbbbb
bba         bbabb    |       bbabbbb            bbabbbbbb
|
|- D3 - bbabb
bbabbbba
```

### Problem 2

What happens if you try to use depth-first search over the state space in problem 1 to solve the example problem?

Answer: The search goes into an infinite loop, exploring longer and longers strings with only D1.

### Problem 3

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.
```empty --- D1 - bbb --- D1 - bbbbbb --- D1 - bbbbbbbbb --- D1 - bbbbbbbbbbbb
empty           bb            bbbb  |          bbbbbb  |           bbbbbbbb
|                  |
|                  |- D2 - abbbbbbbbb
|                            bbbbbbbb
|
|- D2 - abbbbbb   --- D3 - bbabbbbbb
bbbbbb            bbabbbbbb
```

### Problem 4

Suppose that you modify the problem so that any single domino can be used at most K times, for some fixed K. If there are D different dominos, give upper bounds for the depth of the state space, the branching factor, and size of the state space.

Answer: Depth (= maximum number of dominos in a string): KD. Branching factor: D. Size: At most O(DKD)