Future Work

Several research directions using this thesis as a starting point can be identified:

Indexing Constraints.

The current static analysis of grammar rules used as a basis for indexing does not consider type constraints. Future work will investigate an extension of the indexing method in order to accommodate the use of type constraints, with the potential to significantly reduce parsing times.

The Static and Dynamic Cut Definitions.

The definitions for the Static and the Dynamic Cuts are not guaranteed to be maximally specific (although they are probably close), thus it is possible that certain nodes are not included in the Static or Dynamic Cut, and yet can be discarded. The inclusion of such nodes does not affect the formal properties of the Cuts, but it might diminish the improvements brought about by indexing. Future research will investigate various extensions of the Cuts, in order to include all possible nodes.

The Static and Dynamic Cut Implementation.

The theoretical benefits of the Static Cut are exploited in the path indexing method. A possible use of the Static and Dynamic Cut that will be investigated in the future is the replacement of the normal unification between the most general satisfiers of a mother and a daughter with the unification of their Statically Cut most general satisfiers.

Index Implementation.

In this thesis, the indexing is implemented as a hash, a structure that is not always efficient. As mentioned in Section 5.3, several indexing structures (such as B-trees) commonly used in databases are not suitable for parsing. Future research will thoroughly analyze other structures used in databases, and identify the most appropriate one for indexed parsing.

Indexing Strategies.

While the tree-based indexing (overviewed in Section 5.2.3) has poor performance when the number of insertions is quite large, its theoretical benefits cannot be ignored. A possible adaptation of this technique to chart parsing will be studied.

Feature Encoding.

The current method for encoding feature structures proved its efficiency. However, further improvements will be sought that will allow for the representation of different extensions to typed feature structures, such as inequations.

Statistical Improvements.

The purpose of this thesis was not to discredit existing statistical methods. Future work will include the investigation of possible improvements through an integration of statistical methods, such as feature re-ordering or improved quick check tests.

Experimental Evaluation.

At the time of writing this thesis, the only wide-coverage typed feature structure grammar available to the author was the preliminary version of MERGE. In order to thoroughly evaluate the indexing based on static analysis, a much larger experimental set (a larger grammar and a larger test corpus containing no artificially generated sentences) will be sought in the future.