Computational Resources.

In order to measure computational efficiency, the total amount of CPU-time, the maximum amount of CPU-time per input, and the total memory requirements will be measured. Due to differences in hardware, details differ between the two NLP components.

For the data-oriented methods, the CPU-time given is the user-time of the parsing process, in seconds. This measure excludes the time used for system calls made on behalf of the process (this can be ignored). Time was measured on a Silicon Graphics Indigo, with a MIPS R10000 processor, running IRIX 6.2. Memory usage is the maximum number of mega-bytes required, to interpret the 1000 utterances. Regrettably, for a very small percentage (0.02%) of word graphs, the process ran out of memory. This means that the figures for word graph parsing indicate the size of the jobs at the moment the system gave up, which is generally when the physical memory is filled. On the other hand, we should acknowledge the fact that some large word graphs that did receive an interpretation, also approached this limit.

For the grammar-based methods, CPU-time is measured in milliseconds on a HP 9000/780 (running HP-UX 10.20). The system uses SICStus Prolog 3 #3. CPU-time include all phases of processing, but does not contain the time required for system calls (can be ignored) and garbage collection (adds at most 15% for a given run). The memory requirements are given as the increase of the UNIX process size to complete the full run of 1000 inputs. At start-up the process size can be as large as 30 megabytes, so this number has been added in order to estimate total memory requirements.

Table 1: Characterisation of test set (1). This table lists the number of transitions, the number of states, the number of words of the actual utterances, the average number of transitions per word, the maximum number of transitions, and the maximum number of states. The first row provides those statistics for the input word graph; the second row for the so-called normalised word graph in which all $\epsilon$-transitions (to model the absence of sound) are removed. The number of transitions per word is an indication of the extra ambiguity for the parser introduced by the word graphs in comparison with parsing of an ordinary string.

	graphs	trans	states	words	t/w	max(t)	max(s)
input	1000	48215	16181	3229	14.9	793	151
normalised	1000	73502	11056	3229	22.8	2943	128