FD Normalization

The FD accessors and relocation functions, top-gdp, insert-fd and relocate, only work when the FDs are in normal form. Normal form is intuitively the ``shortest notation'' of an FD. For example, the normal form of ((a ((a1 1))) (a ((a2 2))) ({a a3} 3)) is ((a ((a1 1) (a2 2) (a3 3)))). A normal form also does not contain disjunctions. The intention is to define a normal form for input FDs, with no extra nils, maximal factorization of features and no disjunctions.

The function normalize-fd takes as input an arbitrary FD and puts it in normal form. It is abstractely defined as: (normalize-fd fd) = (u nil fd), since the unification function u returns an FD in normal form, and resolves disjunctions.

          
(normalize-fd fd)


Example:
(normalize-fd '((a ((a1 1)))
                (a ((alt (((a1 2))
                          ((a2 2))))))
                (a nil)
                ({a a3} 3)))


->


(a ((a1 1)
    (a2 2)
    (a3 3)))