BibSonomy :: publication ::

tag user group author concept BibTeX key search:all search:diego_ma

The blue social bookmark and publication sharing system.

(0)

This publication has not been reviewed yet.

rating distribution

average user rating

The average rating is computed over all reviews. However, some of them may be invisible to you due to the visibility setting chosen by the reviewers.

(0.0 of 5.0 based on 0 reviews)

Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints

by: Hideki Hirakawa

In: Journal of Natural Language Processing, Vol. 13, Nr. 4 (2006) , p. 3-31.

Abstract

Preference Dependency Grammar PDG is a framework for the morphological, syntactic and semantic analysis of natural language sentences, PDG gives packed shared data structures for emcompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence. This paper proposes the Graph Branch Algorithm for computing the optimum deptendenc tree the most plausible interpretation of a sentence from a scored dependendency forest which is a packed shated data strucutre encompassing all possible dependency trees interpretations of a sentence. The graph branch algorithm adopts the branch and bound principle for managing arbitrary arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG. This paper also reports the espeiment using English texts showing the computational complexity and behavior of the graph branch algorithm.

BibTeX record

@article{Hirakawa:2006,
  abstract = {Preference Dependency Grammar (PDG) is a framework for the morphological, syntactic and semantic analysis of natural language sentences, PDG gives packed shared data structures for emcompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence. This paper proposes the Graph Branch Algorithm for computing the optimum deptendenc tree ( the most plausible interpretation of a sentence) from a scored dependendency forest which is a packed shated data strucutre encompassing all possible dependency trees (interpretations) of a sentence. The graph branch algorithm adopts the branch and bound principle for managing arbitrary arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG. This paper also reports the espeiment using English texts showing the computational complexity and behavior of the graph branch algorithm.},
  added-at = {2007-12-14T02:40:22.000+0100},
  author = {Hirakawa, Hideki},
  biburl = {http://www.bibsonomy.org/bibtex/2b9b5edb603375e5afc421e54f08c1831/diego_ma},
  interhash = {8fc541e72702fce378427119cde418dc},
  intrahash = {b9b5edb603375e5afc421e54f08c1831},
  journal = {Journal of Natural Language Processing},
  keywords = {graphs ambiguity DG},
  number = 4,
  pages = {3-31},
  timestamp = {2007-12-14T02:40:22.000+0100},
  title = {Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints},
  volume = 13,
  year = 2006
}

Endnote record

%0 Journal Article
%1 Hirakawa:2006
%A Hirakawa, Hideki
%D 2006
%J Journal of Natural Language Processing
%K 
%N 4
%P 3-31
%T Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints
%V 13
%X Preference Dependency Grammar (PDG) is a framework for the morphological, syntactic and semantic analysis of natural language sentences, PDG gives packed shared data structures for emcompassing the various ambiguities in each levels of sentence analysis with preference scores and a method for calculating the most plausible interpretation of a sentence. This paper proposes the Graph Branch Algorithm for computing the optimum deptendenc tree ( the most plausible interpretation of a sentence) from a scored dependendency forest which is a packed shated data strucutre encompassing all possible dependency trees (interpretations) of a sentence. The graph branch algorithm adopts the branch and bound principle for managing arbitrary arc co-occurrence constraints including the single valence occupation constraint which is a basic semantic constraint in PDG. This paper also reports the espeiment using English texts showing the computational complexity and behavior of the graph branch algorithm.