Paper: Quasi-Destructive Graph Unification

ACL ID P91-1041
Title Quasi-Destructive Graph Unification
Venue Annual Meeting of the Association of Computational Linguistics
Session Main Conference
Year 1991
  • Hideto Tomabechi (Carnegie Mellon University, Pittsburgh PA; ATR Interpreting Telephony Research Laboratories, Osaka Japan)

Graph unification is the most expensive part of unification-based grammar parsing. It of- ten takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algo- rithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possi- ble. We have developed a scheme to attain these two elements without expensive over- head through temporarily modifying graphs during unification to eliminate copying dur- ing unification. We found that parsing rel- atively long sentences (requiring about 500 top-level unifications during a parse) using our algorithm is approximately twice as fast as parsing the same sentences using Wrob- lewski's algorithm. 1. Motivation Graph unification is...