CSE 675, Spring 2000


Do one of the following, but not both:

  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:

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


Copyright © 2000 by William J. Rapaport (rapaport@cse.buffalo.edu)
file: 675w/hw9.04ap00.html