Implicit and Incremental CSET Specification

CSET specification is the means by which a programmer describes the constituent structure of sentences. Given the importance of this task and its complexity, facilities have been added to FUF to make CSET specification more flexible. It is thus possible to specify implicit and incremental CSETs. This section describes these features of the CSET specification. It presents advanced facilities and can be skipped in first lecture.

The general form of a CSET specification is:

          
(CSET (= c1 ... cn)
      (== b1 ... bm)
      (+ a1 ... ap)
      (- d1 ... dq)))
          
          

The simple syntax (CSET (c1 ... cn)) is equivalent to (CSET (= c1 ... cn)).

As usual in FDs, all of the features of the CSET are optional. Each feature in the CSET feature is named as follows:

• The = sublist is called the absolute CSET.

• The == sublist is called the basis CSET.

• The + and - sublists are the increment CSETs.

The idea behind the use of incremental CSETs is to gradually refine the CSET description, by adding partial information - thus folding the constituent structure description into the general ``partial information, gradual refinement'' methodology of FD specification. The incremental CSET specifications are added to the basis CSET, which can either be specified explicitly, using the == notation, or be the result of the implicit CSET inference described above.

The actual CSET of an FD is computed by applying the following procedure:

1.

If the absolute CSET (=) is present, it becomes the value of the actual CSET. The absolute CSET feature is used when you want to disable all incremental computations.

2.

Else: If the basis-CSET is present,

(a)

let BSET = basis-CSET, else let BSET = the implicit CSET, computed as described above (from pattern and cat inspection).

(b)

If the +increment-CSET is present, let BSET = BSET union +increment.

(c)

If the -increment-CSET is present, let BSET = BSET - -increment (set difference).

(d)

Return BSET as the actual CSET.

The result of this procedure is a list of absolute paths, pointing to the sub-constituents of the current constituent. In all cases, this actual cset is ``cleaned up'' by applying the following procedure:

• All duplicate paths are removed. Two paths are duplicate if they point to the same FD. That is, even if the paths are distincts but they point to conflated FDs, they are considered duplicates in the CSET.

• All leaf-constituents are removed. A leaf-constituent is a constituent whose value is not a list of pairs - for example, a symbol or a string. The idea is that there is no point in recursing on a leaf-constituent.

• All constituents which are conflated with a -increment constituent are also removed from the actual cset.

The following grammar fragments illustrate briefly the use of incremental CSET specification.⁶

          
((cat clause)
 (cset (== prot verb))
 (alt (((prot given)
        (subject {^ prot})
        (voice active))
       ((prot none)
        (goal given)
        (cset (- prot) (+ goal))
	(subject {^ goal})))))
          
          

The first cset feature specifies that the basis cset for this clause constituent should not be the implicit cset (derived from pattern and cat), but instead the explicit list (prot verb). In the second cset feature, this basis cset is incrementally refined by specifying that when prot in none, prot is not part of the cset and instead goal is added to the cset. If prot is a non-leaf constituent, then the actual cset for this example will be (prot verb), if it is none, then it will be (verb goal).

          
((cat clause)
 (subject ((cat np)))
 (prot {^ subject})
 (cset (- prot)))
          
          

In this second fragment, no absolute cset is specified (no = feature) and no basis cset is present (no == feature). Therefore the implicit cset is computed and is found to be (subject) (because of the presence of the (cat np) feature under subject). (subject) is thus the initial basis-cset. The incremental cset (- prot) is then added to the cset. The basis-cset remains (subject) at this point. Finally, the cset is ``cleaned'' - and it is found that prot and subject are duplicates of each other because of the conflation (prot {^ subject}). Since prot is member of the -increment list, its ``synonyms'' are deleted from the basis cset, and the actual cset is found to be empty ().

The computation of implicit and incremental CSETs can interact with the more advanced control features of goal freezing (with the wait construct). These interactions are described in Sect..