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.