Homework # 11
due Tuesday, April 19, 3:30 PM

Searching

The following predicate is a helper predicate for flattening a tree into a list:

flattenH(leaf(X),L,[X|L]).
flattenH(branch(V,W),L,N) :- flattenH(W,L,M), flattenH(V,M,N).

In this question, you are going to trace the solution of flattenH(T,[],[1,2,3]). You need to carefully go through every step of the algorithm on page 428, with the changes for variable renaming described on pages 433-435. We will do this in pieces.

Unification

Solve the following unification problems. Either give a/the MGU, or indicate that the unification failed.

1. unify(flattenH(leaf(X1),L1,[X1|L1]),flattenH(T,[],[1,2,3]))
2. unify(flattenH(branch(V2,W2),L2,N2),flattenH(T,[],[1,2,3]))
3. unify(flattenH(leaf(X3),L3,[X3|L3]),flattenH(W2,[],M2))
4. unify(flattenH(branch(V4,W4),L4,N4),flattenH(W2,[],M2))

Resolution

Solve the following resolution problems. As part of resolution, you may do unification. If the unification is one you solved in the previous section, you can use the results directly by referring to one of unify$_1$, unify$_2$, unify$_3$ and unify$_4$. Otherwise, indicate a new unification problem and solve it.

1. resolution([flattenH(leaf(X1),L1,[X1|L1])], [flattenH(T,[],[1,2,3])])

2. resolution([flattenH(branch(V2,W2),L2,N2),
               flattenH(W2,L2,M2),
               flattenH(V2,M2,N2)],
              [flattenH(T,[],[1,2,3])])
   

3. resolution([flattenH(leaf(X3),L3,[X3|L3])],
              [flattenH(W2,[],M2), flattenH(V2,M2,[1,2,3])])
   

Do not confuse unification with resolution!

Solve

Using the previous steps to give the whole proof tree trace up to the first success for the following call. Please trace every call to solve, resolution and unify, even ones that fail.

solve([flattenH(T,[],[1,2,3])])

Assume that the entire rule database consist of those two rules for flattenH.

Analysis

After this first success, the proof tree goes on forever without any more success. (Try it in Prolog!) Why?

Cost Models

Do the following exercises from Chapter 21 on paper: Exercises 21.1-3.

About this document