@inproceedings{tomabechi-1991-quasi,
title = "Quasi-Destructive Graph Unification",
author = "Tomabechi, Hideto",
editor = "Tomita, Masaru and
Kay, Martin and
Berwick, Robert and
Hajicova, Eva and
Joshi, Aravind and
Kaplan, Ronald and
Nagao, Makoto and
Wilks, Yorick",
booktitle = "Proceedings of the Second International Workshop on Parsing Technologies",
month = feb # " 13-25",
year = "1991",
address = "Cancun, Mexico",
publisher = "Association for Computational Linguistics",
url = "https://aclanthology.org/1991.iwpt-1.19",
pages = "164--171",
abstract = "Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90{\%} of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two criteria without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. The temporary modification is invalidated in constant time and therefore, unification can continue looking for a failure without the overhead associated with copying. After a successful unification because the nodes are temporarily prepared for copying, a fast copying can be performed without overhead for handling reentrancy, loops and variables. We found that parsing relatively long sentences (requiring about 500 unifications during a parse) using our algorithm is 100 to 200 percent faster than parsing the same sentences using Wroblewski{'}s algorithm.",
}
<?xml version="1.0" encoding="UTF-8"?>
<modsCollection xmlns="http://www.loc.gov/mods/v3">
<mods ID="tomabechi-1991-quasi">
<titleInfo>
<title>Quasi-Destructive Graph Unification</title>
</titleInfo>
<name type="personal">
<namePart type="given">Hideto</namePart>
<namePart type="family">Tomabechi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">author</roleTerm>
</role>
</name>
<originInfo>
<dateIssued>1991-feb 13-25</dateIssued>
</originInfo>
<typeOfResource>text</typeOfResource>
<relatedItem type="host">
<titleInfo>
<title>Proceedings of the Second International Workshop on Parsing Technologies</title>
</titleInfo>
<name type="personal">
<namePart type="given">Masaru</namePart>
<namePart type="family">Tomita</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Martin</namePart>
<namePart type="family">Kay</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Robert</namePart>
<namePart type="family">Berwick</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Eva</namePart>
<namePart type="family">Hajicova</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Aravind</namePart>
<namePart type="family">Joshi</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Ronald</namePart>
<namePart type="family">Kaplan</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Makoto</namePart>
<namePart type="family">Nagao</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<name type="personal">
<namePart type="given">Yorick</namePart>
<namePart type="family">Wilks</namePart>
<role>
<roleTerm authority="marcrelator" type="text">editor</roleTerm>
</role>
</name>
<originInfo>
<publisher>Association for Computational Linguistics</publisher>
<place>
<placeTerm type="text">Cancun, Mexico</placeTerm>
</place>
</originInfo>
<genre authority="marcgt">conference publication</genre>
</relatedItem>
<abstract>Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two criteria without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. The temporary modification is invalidated in constant time and therefore, unification can continue looking for a failure without the overhead associated with copying. After a successful unification because the nodes are temporarily prepared for copying, a fast copying can be performed without overhead for handling reentrancy, loops and variables. We found that parsing relatively long sentences (requiring about 500 unifications during a parse) using our algorithm is 100 to 200 percent faster than parsing the same sentences using Wroblewski’s algorithm.</abstract>
<identifier type="citekey">tomabechi-1991-quasi</identifier>
<location>
<url>https://aclanthology.org/1991.iwpt-1.19</url>
</location>
<part>
<date>1991-feb 13-25</date>
<extent unit="page">
<start>164</start>
<end>171</end>
</extent>
</part>
</mods>
</modsCollection>
%0 Conference Proceedings
%T Quasi-Destructive Graph Unification
%A Tomabechi, Hideto
%Y Tomita, Masaru
%Y Kay, Martin
%Y Berwick, Robert
%Y Hajicova, Eva
%Y Joshi, Aravind
%Y Kaplan, Ronald
%Y Nagao, Makoto
%Y Wilks, Yorick
%S Proceedings of the Second International Workshop on Parsing Technologies
%D 1991
%8 feb 13 25
%I Association for Computational Linguistics
%C Cancun, Mexico
%F tomabechi-1991-quasi
%X Graph unification is the most expensive part of unification-based grammar parsing. It often takes over 90% of the total parsing time of a sentence. We focus on two speed-up elements in the design of unification algorithms: 1) elimination of excessive copying by only copying successful unifications, 2) Finding unification failures as soon as possible. We have developed a scheme to attain these two criteria without expensive overhead through temporarily modifying graphs during unification to eliminate copying during unification. The temporary modification is invalidated in constant time and therefore, unification can continue looking for a failure without the overhead associated with copying. After a successful unification because the nodes are temporarily prepared for copying, a fast copying can be performed without overhead for handling reentrancy, loops and variables. We found that parsing relatively long sentences (requiring about 500 unifications during a parse) using our algorithm is 100 to 200 percent faster than parsing the same sentences using Wroblewski’s algorithm.
%U https://aclanthology.org/1991.iwpt-1.19
%P 164-171
Markdown (Informal)
[Quasi-Destructive Graph Unification](https://aclanthology.org/1991.iwpt-1.19) (Tomabechi, IWPT 1991)
ACL
- Hideto Tomabechi. 1991. Quasi-Destructive Graph Unification. In Proceedings of the Second International Workshop on Parsing Technologies, pages 164–171, Cancun, Mexico. Association for Computational Linguistics.