首页    期刊浏览 2024年12月11日 星期三
登录注册

文章基本信息

  • 标题:Grammar Factorization by Tree Decomposition
  • 本地全文:下载
  • 作者:Daniel Gildea
  • 期刊名称:Computational Linguistics
  • 印刷版ISSN:0891-2017
  • 电子版ISSN:1530-9312
  • 出版年度:2011
  • 卷号:37
  • 期号:1
  • 页码:231-248
  • DOI:10.1162/coli_a_00040
  • 语种:English
  • 出版社:MIT Press
  • 摘要:We describe the application of the graph-theoretic property known as treewidth to the problem of finding efficient parsing algorithms. This method, similar to the junction tree algorithm used in graphical models for machine learning, allows automatic discovery of efficient algorithms such as the O(n4) algorithm for bilexical grammars of Eisner and Satta. We examine the complexity of applying this method to parsing algorithms for general Linear Context-Free Rewriting Systems. We show that any polynomial-time algorithm for this problem would imply an improved approximation algorithm for the well-studied treewidth problem on general graphs.
国家哲学社会科学文献中心版权所有