Paper: Quasi-Destructive Graph Unification With Structure-Sharing

ACL ID C92-2068
Title Quasi-Destructive Graph Unification With Structure-Sharing
Venue International Conference on Computational Linguistics
Session Main Conference
Year 1992

Graph unifi(:ation remains the nlost expensive part of unificatiou-b~Lsed grammar l)arsing. We fl)cus on (Hie 81}ee(l-u 1) elelltellt ill the design of llllifiea- tion algorithms: avoidance of copying of umao(li- fled sul)graph.s. We propose a method of attaining snch a design through a nlethod of structnre-sharing which avoids log(d) overheads often associated with structure-sharillg of graphs without any use of costly dependency pointers. The proposed scheme elimi- nates redundant copying whih~ maintaining the dc,qtructive scheme's ability to avoid over copying and early copying eomlfined with its ability to handle cyclk: structures without algorithnfie additions. 1 Motivation Despite recent efforts in improving graph unification algorithms, graph unification renlains the most ex...