... databases^1.1

Indexing is one of the most popular research topics in databases. Presentations of existing indexing methods can be found in the vast database literature, from introductory textbooks ([Elmasri and Navathe2000]) to advanced research topics ([Bertino et al.1997,Manolopoulos et al.1999]).

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

...cat^3.1

There is a distinction between upper and lower case. It is common to HPSG to have features and feature values bearing the same name.

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

... chart^3.2

A discussion about TFSG parsing is presented in Section 4.1.

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

... reason^3.3

The reason ALE and other similar systems are implemented in Prolog is thoroughly explained in [Penn2000] and [Penn and Munteanu2003].

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

... improvements^4.1

However, the main advantage of using a non-statistical method is the absence of the training phase, resulting in faster parser set-up times.

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

... mother^6.1

Throughout this section, mother $M$ and daughter $D$ are TFSs and denote the MGSat of a mother description and of a daughter description.

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

... words^7.1

The coverage of this version of the MERGE grammar is quite limited, therefore the test sentences are rather short.

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

... examples^7.2

This example is independent of the one presented in Table 7.1.

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

... seen^7.3

In order to maintain the clarity of these graphs, quick-check parsing times are reported separately than positional and path indexing parsing times.

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

... small^7.4

For example, the lexical entry for the proper noun kim has 13 feature-value pairs in Alvey, while in MERGE it has 206.

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

... unifications^7.5

100% represents the ratio of successful unifications in the chart, without counting the failed unifications between index keys, when looking for the correct hash entry for a daughter or an edge.

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