Paper: Efficient Disjunctive Unification For Bottom-Up Parsing

ACL ID C90-3013
Title Efficient Disjunctive Unification For Bottom-Up Parsing
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1990

This paper describes two novel techniques which, when applied together, in practice significantly re- duce the time required for unifying disjunctive fea- ture structures. The first is a safe but fast method for discarding irrelevant disjunctions from newly- created structures. The second reduces the time re- quired to check the consistency of a structure from exponential to polynomial in the number of disjunc- tions, except in cases that, it will be argued, should be very unusual in practical systems. The techniques are implemented in an experimental Japanese anal- yser that uses a large, existing disjunctive Japanese grammar and lexicon. Observations of the time be- haviour of this analyser suggest that a significant speed gain is achieved.