Graph Branch Algorithm: An Optimum Tree Search Method for Scored Dependency Graph with Arc Co-occurrence Constraints
スポンサーリンク
概要
- 論文の詳細を見る
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 encompassing 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 dependency tree (the most plausible interpretation of a sentence) from a scored dependency forest which is a packed shared data structure 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 experiment using English texts showing the computational complexity and behavior of the graph branch algorithm.
- Information and Media Technologies 編集運営会議の論文
Information and Media Technologies 編集運営会議 | 論文
- Optimal Balanced Semi-Matchings for Weighted Bipartite Graphs
- A Quantitative Evaluation Methodology of Interconnection Networks
- Proposal and Performance Evaluation of Hash-based Authentication for P2P Network
- Resolving Direct and Indirect Anaphora for Japanese Definite Noun Phrases
- Ring Signatures: Universally Composable Definitions and Constructions