Disjunctive form



next up previous
Next: Our dictionary language Up: Notation and terminology Previous: Meta-rules

Disjunctive form

The use of formulas to specify a link grammar dictionary is convenient for creating natural language grammars, but it is cumbersome for mathematical analysis of link grammars, and in describing algorithms for parsing link grammars. We therefore introduce a different way of expressing a link grammar called disjunctive form.

In disjunctive form, each word of the grammar has a set of disjuncts associated with it. Each disjunct corresponds to one particular way of satisfying the requirements of a word. A disjunct consists of two ordered lists of connector names: the left list and the right list. The left list contains connectors that connect to the left of the current word (those connectors end in -), and the right list contains connectors that connect to the right of the current word. A disjunct will be denoted: (() ())

Where are the connectors that must connect to the left, and are connectors that must connect to the right. The number of connectors in either list may be zero. The trailing + or - may be omitted from the connector names when using disjunctive form, since the direction is implicit in the form of the disjunct.

To satisfy the linking requirements of a word, one of its disjuncts must be satisfied (and no links may attach to any other disjunct). To satisfy a disjunct all of its connectors must be satisfied by appropriate links. The words to which , , are linked are to the left of the current word, and are monotonically increasing in distance from the current word. The words to which , , are linked are to the right of the current word, and are monotonically increasing in distance from the current word.

It is easy to see how to translate a link grammar in disjunctive form to one in standard form. This can be done simply by rewriting each disjunct as ( =13& =13& =13& =13& =13& =13& =13& )

and combining all the disjuncts together with the =13or operator to make an appropriate formula.

It is also easy to translate a formula into a set of disjuncts. This is done by enumerating all ways that the formula can be satisfied. For example, the formula: =13(A- =13or ()) =13& D- =13& (B+ =13or ()) =13& (O- =13or S+)

corresponds to the following eight disjuncts:



next up previous
Next: Our dictionary language Up: Notation and terminology Previous: Meta-rules




Thu Oct 12 13:01:13 EDT 1995