FDs as Graphs

When the structure of an FD becomes complex, and more conflations with paths are introduced, a visual representation of the FD becomes extremely useful. This visual representation also provides a clear interpretation of the path mechanism and makes reading of relative path much easier. The structured format of FDs can be viewed as equivalent to a directed graph with labeled arcs as pointed out in [#!Karttunen-84!#]. The correspondence is established as follows: an FD is a node, each pair (attr value) is a labeled arc leaving this node. The attr of the pair is the label of the arc, the value is the adjacent node. Internal nodes in the graph have therefore no label whereas leaves are atomic values. The equivalence is illustrated in Fig..

Figure: FD as a graph

The graph notation is particularly useful to interpret relative paths. When a relative path occurs somewhere in an FD, its destination can be identified by going up on the arcs, one arc for each `^'. When the value of a pair is a path, e.g., (a {b}), then the corresponding arc actually points to the same node as the given path. In this case, there is structure sharing between a and b. This configuration is illustrated in Fig., where the paths {action number} and {agent number} are conflated, as well as the paths {affected lex} and {affected head lex} and {subject} and {agent}.

Figure: Conflation in an FD graph

The conflation of {subject} with {agent} makes all the paths that are extensions of either agent or subject equivalent. For example, {agent lex} and {subject lex} are equivalent. This equivalence is easily read in the graph notation.

Figure: A grammar for conjunction

     The graph notation also makes it clear that the up-arrow notation can be ambiguous. Whenever a Y configuration is met in the graph, for example in the two black nodes in Fig., the up-arrow does not specify which branch of the Y must be taken. This problem is illustrated in the grammar in Fig.. The FD is extracted from a grammar dealing with conjunction. The constraint enforced by the grammar is that all the conjuncts in a conjunction must have the same syntactic category. A conjunction is represented by an FD with two constituents: head represents the conjunction as a whole as a constituent and list is a list of conjuncts. The list is represented in a singly-linked list of elements, with a recursive FD containing at each level the first element of the list (feature car) and the rest of the list (feature cdr). In Fig., the path c1 is used to point to the first constituent of the list. c1 is therefore defined by the equation {c1} = {list car}. The grammar in LISP notation is shown below along with a sample input:

          


GR =	((c1 {^ list car})
	 (c1 ((cat {^ ^ head cat}))))


IN =	((head ((cat np)))
	 (list ((car ((lex `cat')))
		(cdr ((car ((lex `dog')))
	              (cdr none))))))


          
          

The underlined line corresponds to the black dot in the graph notation shown in Fig.. The problem is to interpret where the relative path {^ ^ head cat} is pointing to. The notation is ambiguous between {head cat} and {list head cat}, depending on whether one considers the black dot as being located at address {c1} or {list car}. This ambiguity is solved in FUF by following the convention that up-arrows always refer to the textual location where they appear in the grammar. So in this example, the up-arrows refer to the address {c1 cat} and not to the address {list car cat} because they are written as a pair (c1 ((cat {^ ^ head cat}))) and not as (list ((car ((cat {^ ^ head cat}))))).

There are special attributes and values which cannot be drawn in this graph notation because they have a special unification behavior. These are, for attributes: alt, opt, ralt, pattern, cset, fset, test, control and cat (or the currently specified cat attribute) and for values: none, any and given. The special constructs #(under x) and #(external y) have also a special meaning for the unifier. These are all the ``keywords'' known by the unifier. They are presented in the following sections.