... structure.¹

Other structures are the main-clause and head-filler structure. These are discussed in the sections on main-clause syntax and topicalisation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... follows:²

There is an additional rule, for constructing subordinate clauses with a missing (`extracted') subject. This rule ( sbar2) could be used in an account of nonlocal dependencies which allows for extraction out of subordinate clauses as well.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... empty.³

The lexical rule which moves complements from SC to SLASH does not apply to verbal traces. Instead, it can be applied to the finite verb which `binds' the trace. Also, if a verbal gap combines with a complement having a non-empty SLASH, the relevant passing on of the SLASH value is handled by the finite verb which binds the trace. This is possible because the SC-list of the verbal trace and the binder will be shared.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... index,⁴

In the original formalism indices and variables are distinguished. An index uniquely identifies a term expression. At this moment indices and variables have the same function in our implementation. We may need to distinguish between them later.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...QUANT⁵

In chapter 5 of [17] term expressions also contain a slot CAT for specifying information about the lexical form and syntactic/semantic type of an expression (e.g. quantifier, pronoun, etc.) and a slot REF for specifying the (contextual) referent of an expression. We do use CAT, but have omitted it from the presentation below. We currently do not use REF.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... following:⁶

In chapter 5 of [17] two more formula constructs are introduced. These are not used in the current implementation.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... weight.⁷

We do not define a weight function on edges, but we specify how weights are updated if a path is extended, for generality. This approach allows e.g. for the possibility that different cost components employ different operations for combining weights. For example, some cost components may use addition (e.g. for weights which are expressed as negative logarithms derived from probabilities), whereas other cost components may require multiplication (e.g. for probabilities).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...).⁸

This compares well with the O(V³) complexity which can be obtained for most parsers.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

...algorithms. ⁹

Note that the algorithm is different from the Viterbi algorithm. The latter algorithm finds the best path through a possibly cyclic weighted graph, for a given sequence of observed outputs. In the current application we require an algorithm to find the best path in an acyclic weighted graph (without an additional observed output sequence).

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.

... expression.¹⁰

For the grammar-based methods, CPU-time was measured on a HP 9000/780 machine running HP-UX 10.20, with SICStus Prolog 3 patch level 3. The statistics for the data-oriented module were obtained on a Silicon Graphics Indigo with a MIPS R10000 processor, running IRIX 6.2.

.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.