文章基本信息

标题：Synchronous Context-Free Grammars and Optimal Parsing Strategies
本地全文：下载
作者：Daniel Gildea ; Giorgio Satta
期刊名称：Computational Linguistics
印刷版ISSN：0891-2017
电子版ISSN：1530-9312
出版年度：2016
卷号：42
期号：2
页码：207-243
DOI：10.1162/COLI_a_00246
语种：English
出版社：MIT Press
摘要：The complexity of parsing with synchronous context-free grammars is polynomial in the sentence length for a fixed grammar, but the degree of the polynomial depends on the grammar. Specifically, the degree depends on the length of rules, the permutations represented by the rules, and the parsing strategy adopted to decompose the recognition of a rule into smaller steps. We address the problem of finding the best parsing strategy for a rule, in terms of space and time complexity. We show that it is NP-hard to find the binary strategy with the lowest space complexity. We also show that any algorithm for finding the strategy with the lowest time complexity would imply improved approximation algorithms for finding the treewidth of general graphs.