1992 · 18 citations · 9 references
ComputingComputer ScienceCompilersData StructuresNatural Language ProcessingAbstract Syntax TreesGrammarGraph AlgorithmsParsingSyntactic ParsingSyntax ParsingAbstract Syntax Tree ConstructionGraph CompilationGraph RewritingGraph TransformationUnification
Graph unification remains the most expensive part of unification-based grammar parsing. We focus on one speed-up element in the design of unification algorithms: avoidance of copying of unmodified subgraphs. We propose a method of attaining such a design through a method of structure-sharing which avoids log(d) overheads often associated with structure-sharing of graphs without any use of costly dependency pointers. The proposed scheme eliminates redundant copying while maintaining the quasi-destructive scheme's ability to avoid over copying and early copying combined with its ability to handle cyclic structures without algorithmic additions.
9
Lauri Karttunen · 1986 · 79 citations · Full text
Structure sharing with binary trees
Lauri Karttunen, Martin Kay · 1985 · 40 citations · Full text
Quasi-destructive graph unification
Hideto Tomabechi · 1991 · 37 citations · Full text
Language Studies, Computer Science, Computational Linguistics +11