David Carter
Efficient Disjunctive Unification in a Bottom-Up
Shift-Reduce
Parser
Abstract:This report describes two novel techniques which, when applied together, in practice
significantly reduce the time required for unifying disjunctive feature structures. The
first is a safe but fast method for discarding irrelevant disjunctions from
newly-created structures. The second reduces the time behaviour of checking
the consistency of a structure from exponential to polynomial in the number of
disjunctions, except in cases that, it will be argued, should be very unusual in practical systems.
The techniques are implemented in Propane, an experimental Japanese
analyser that uses the large, existing disjunctive Japanese and lexicon created for the
Nadine system. Propane is a shift-reduce parser whose behaviour is guided by the
preference in Japanese for left-branching structures.
The effectiveness of both the parsing and unification strategies is assessed. The
results suggest that the parsing algorithm combines the expected efficiency with a
promising degree of accuracy, while the time required or unification is much reduced from that
of exponential algorithms.