HW #9: UNIFICATION

1. Hand-trace the unification of (11.22) (p. 420) using the unification algorithm in Fig. 11.8. Do this by making a table with at least 2 columns. (If you want to use more columns for other information, that's fine.) Column 1 should list the step of the algorithm being executed. Column 2 should show the DAG after that step has been executed. (The initial DAG is shown in Fig. 11.5; the final, unified DAG is shown in Fig. 11.7.) If you find this exercise to be too trivial, then do the same thing for (11.23).

2. Revise Kay's standard unification algorithm for expressions of the form f(a1,...,an), f(b1,...,bn) so that it applies to feature structures (FS) without having to translate them into DAGs (as our text does). I think there are 2 ways to go about this:
   Suggestion 1: First give an algorithm for translating FSs into functional notation so that the standard algorithm applies directly. Maybe something like this will work?:

           | f1 v1 |  ->   f( f1(v1) f2(v2) )
           | f2 v2 |
   

   Note that Kay's algorithm (indeed, all standard unification algorithms) require both expressions to be unified to be of the same arity.

   Suggestion 2: Modify Kay's standard unification algorithm so that it applies directly to FSs.

   In any case, be sure to test your algorithm all all examples in the book.

DUE: MONDAY, APRIL 17